그릴 암호

16세기에는 오늘날과 같은 컴퓨터가 없었지만, 그때에도 메시지를 엉뚱한 사람이 읽지 못하도록 보호할 필요가 있었다. 노예의 머리를 밀어 두피에 메시지를 적고, 머리카락이 다시 자랄 때까지 기다렸다가 적진을 통과시켜 전달하는 것과 같은 옛 방법도 통하기는 했지만 시간이 너무 오래 걸렸다. 그래서 더 빠른 방법이 필요했다. 그중 하나가 이탈리아 수학자 지롤라모 카르다노(Girolamo Cardano)가 처음 기술한 그릴(grille) 암호이다.

암호화와 복호화 모두 그릴이라 부르는 도구(암호 키)를 사용하며, 두 사람은 같은 그릴을 가지고 있어야 한다. 그릴은 $N \times N$개의 단위 칸으로 이루어진 정사각형 격자이며, 일부 칸은 막혀 있고 일부 칸은 뚫려 구멍을 이룬다.

그릴에 구멍이 $m$개 있다고 하자. 암호화할 때는 먼저 메시지의 첫 $m$개 글자를 구멍에 적는데, 위에서 아래로 행 단위로, 각 행 안에서는 왼쪽에서 오른쪽 순서로 적는다. 그다음 그릴을 시계 방향으로 90도 회전시키고 같은 읽기 순서로 다음 $m$개 글자를 구멍에 적는다. 다시 한 번 회전시켜 또 $m$개를 적고, 한 번 더 회전시켜 마지막 $m$개를 적는다. 그러고도 빈 칸이 남으면 암호문이 더 안전해 보이도록 아무 글자로 채운다. 회전하는 것은 그릴이지 메시지가 아니라는 점에 유의하라.

복호화할 때는 같은 절차를 따르되, 구멍을 통해 글자를 적는 대신 읽는다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 하나의 그릴과 하나의 암호문을 기술한다.

각 테스트 케이스는 그릴의 크기 $N$ ($1 \le N \le 1000$)이 적힌 줄로 시작한다. 이어지는 $N$개의 줄은 그릴을 나타내며, 각 줄은 정확히 $N$개의 문자로 이루어지고 각 문자는 #(막힌 재질) 또는 O(대문자 O, 구멍) 중 하나이다.

실제로는 그릴의 구멍이 암호문의 같은 위치를 두 번 이상 사용하지 않도록 배치된다. 하지만 이 문제에서는 그것이 보장되지 않는다. 회전을 거친 뒤 여러 구멍이 암호문의 같은 위치에 놓일 수도 있다. 그래도 복호화 절차는 동일하다.

그릴 다음에는 암호문을 담은 $N$개의 줄이 이어지며, 각 줄은 정확히 $N$개의 대문자로 이루어진다.

마지막 테스트 케이스 다음에는 0 하나만 적힌 줄이 온다.

각 테스트 케이스마다 복호화한 메시지를 공백 없이 한 줄에 출력하라.