В Квадратной стране никогда не было трамваев. Конечно, это не могло не волновать население. И вот на только что проведенном референдуме народ высказался за строительство трамвайной сети по всей стране, а также за то, чтобы эта сеть была связана с трамвайной сетью соседней Прямоугольной страны. Народ проголосовал — значит надо строить. Но уже на стадии проектирования возникла проблема, связанная с тем, что системы координат Квадратной и Прямоугольной стран различаются, более того, у них даже координатные оси не параллельны.

Президент Квадратной страны посовещался с Квадратной Думой и принял историческое решение: повернуть систему координат своей страны относительно точки (0, 0) на угол α по часовой стрелке. Решение оказалось весьма непопулярным — ведь в Квадратной стране все участки, находящиеся в частной собственности, представляют собой наборы квадратов со сторонами, параллельными осям, и вершинами с целочисленными координатами. Выходит, что после поворота придется изменить границы частных владений. Порядок установки новых границ был утвержден указом Президента. Собственник заново определяется для каждой клетки единичного размера. Если некоторый собственник владел до поворота более чем половиной этой клетки, то он становится владельцем всей клетки. Если же такого собственника нет, то вся клетка отходит государству.

Квадратное Правительство поручило вам автоматизировать перераспределение частной собственности. Вам дана карта, на которой отмечены все нынешние частные владения. Требуется построить карту, где будут отмечены все частные владения после поворота.

Так как земли, расположенные далеко от центра, не пользуются спросом, все частные владения в Квадратной стране расположены внутри квадрата [−n, n] × [−n, n]. Схема владений представляет собой квадратную таблицу, в каждой ячейке которой записан уникальный код владельца соответствующей клетки — строчная латинская буква. Если в ячейке стоит точка, то соответствующая клетка принадлежит государству. На схеме ось x направлена слева направо, а ось y — снизу вверх.

В первой строке через пробел записаны два числа: n и α; 1 ≤ n ≤ 30; 0 ≤ α ≤ 90; угол α дан в градусах. В следующих 2n строках записано по 2n символов, образующих схему владений квадрата [−n, n] × [−n, n].

После поворота некоторые частные владения уже могут не попасть в квадрат [−n, n] × [−n, n], поэтому выведите в том же формате схему владений квадрата [−2n, 2n] × [−2n, 2n] после поворота координат и перераспределения собственности.