Damir likes to rotate. Right now he is rotating tables of letters. He wrote an $R\times C$ table onto a piece of paper. He has also chosen an angle $K$, a multiple of $45$, and wants to rotate his table that many degrees clockwise.

It turns out this task is a bit too hard for Damir, so help him out.

-----Input-----
The first line contains two integers $R$ and $C$ separated by a space ($1 \leq R \leq 10$, $1 \leq C \leq 10$), the number of rows and columns in Damir’s table. Each of the next $R$ lines contains one row of Damir’s table, a string of $C$ lowercase letters. The last line contains an integer $K$, a multiple of $45$ between $0$ and $360$ (inclusive).

-----Output-----
Output Damir’s table rotated $K$ degrees clockwise, like shown in the examples. The output should contain the smallest number of rows necessary. Some rows may have leading spaces, but no rows may have trailing spaces.

-----Examples-----
Sample Input 1:
3 5
damir
marko
darko
45
Sample Output 1:
  d
 m a
d a m
 a r i
  r k r
   k o
    o

Sample Input 2:
3 5
damir
marko
darko
90
Sample Output 2:
dmd
aaa
rrm
kki
oor

Source: kattis | Difficulty: MEDIUM
Tags: String algorithms


Solutions: