Rotating the Character Table

Given a table of characters with r rows and c columns, output the state of the table after rotating it clockwise by k degrees, where k is guaranteed to be a multiple of 45.

Note that a rotation of 45° (or any angle that is 45° modulo 90°) does not simply swap rows and columns. In particular, when rotating by 45° the new table will have dimensions r+c-1 × r+c-1 and the mapping from the original cell at index (i, j) (0-indexed) to the rotated table is given by:

[ newRow = i + j, \quad newCol = j - i + (r - 1). ]

For rotations that are not 45° exactly (but are still multiples of 45), you may first perform the appropriate number of 90° clockwise rotations (using the standard transformation) and then, if needed, perform one final 45° clockwise rotation using the formula above.

The standard 90° clockwise rotation transforms a table of size R × C into a table of size C × R according to:

[ new[i][j] = old[R-1-j][i]. ]

inputFormat

The first line contains three integers r, c and k where 1 ≤ r, c ≤ 100 and k is a multiple of 45 (0 ≤ k ≤ 360, k may exceed 360).

The following r lines each contain a string of length c representing the table.

outputFormat

Output the rotated table. For a 45° (or composite) rotation, if the new table dimensions are n × n, output n lines each containing n characters. Spaces should be preserved.

sample

3 3 45
abc
def
ghi

  a  
d b
g e c
h f
i