그릴에 무엇이 보이는가?

그릴 암호는 1550년에 지롤라모 카르다노가 처음 설명한 기법이다. 여기서 다루는 방식은 1800년대 후반에 나왔고, 다음과 같이 동작한다. 암호로 바꿀 메시지를 $n \times n$ 격자에 위에서 아래로 한 행씩 적고, 구멍이 뚫린 카드를 격자 위에 덮는다. 이 카드가 그릴이다.

암호화는 구멍으로 보이는 글자를 행 순서대로 적으면서 시작한다. 그다음 그릴을 시계 방향으로 90도 돌려 새로 보이는 글자를 이어 적고, 같은 과정을 두 번 더 반복한다. 메시지의 모든 글자가 언젠가 구멍에 나타나도록 구멍을 골라야 하는데, 이런 배치를 만들기는 어렵지 않다.

아래 그림은 "Send more monkeys"에 임의의 글자 하나를 덧붙여 채운 격자를 "noeesrksdmnyemoj"로 암호화하는 과정이다.

그림 I.1

메시지가 격자보다 길면 앞의 $n^2$개 글자를 격자에 적어 암호화하고, 이어지는 $n^2$개 글자를 다시 암호화하는 식으로 진행하며, 마지막 격자는 필요하면 임의의 글자로 채운다. 이 문제에서는 길이가 정확히 $n^2$인 메시지만 다룬다.

암호문과 암호화에 쓴 그릴이 주어지면 원래 메시지를 복원하라. 조건이 하나 더 붙는다. 주어진 그릴이 올바르지 않을 수 있다. 즉 네 번의 회전 동안 구멍이 격자의 모든 칸을 정확히 한 번씩 드러내지 못하는 경우가 있다. 이때는 복호화할 수 없다고 알려야 한다.

첫 줄에 격자와 그릴의 크기를 나타내는 양의 정수 $n$이 주어진다. ($n \le 10$)

다음 $n$개 줄에 그릴이 주어진다. 구멍은 ., 구멍이 아닌 칸은 X로 표시한다.

마지막 줄에 소문자 알파벳으로만 이루어진 암호문이 주어진다. 이 줄의 길이는 항상 $n^2$이다.

복호화한 문자열을 공백 없이 한 줄에 출력한다. 그릴이 올바르지 않으면 invalid grille을 출력한다.