COCI 2008/2009, Contest #4

Task ROT

Damir likes to rotate. Right now he is rotating tables of letters. He wrote an R×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 ≤ R ≤ 10, 1 ≤ C ≤ 10) the numberof 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

Input

3 5
damir
marko
darko
45

Output

  d
 m a
d a m
 a r i
  r k r
   k o
    o

Input

3 5
damir
marko
darko
90

Output

dmd
aaa
rrm
kki
oor

Input

5 5
abcde
bcdef
cdefg
defgh
efghi
315

Output

    e
   d f
  c e g
 b d f h
a c e g i
 b d f h
  c e g
   d f
    e

All Submissions
Best Solutions


Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Jan 19, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...