마법 스위치

정사각형 칸으로 나뉜 직사각형 판이 있다. 행은 $3$개, 열은 $3M + 1$개이며 $M$은 양의 정수다. 행에는 위에서 아래로 $1$부터 $3$까지, 열에는 왼쪽에서 오른쪽으로 $1$부터 $3M + 1$까지 번호를 붙인다. $i$행 $j$열의 칸을 $(i, j)$로 쓴다.

각 칸은 바닥이거나 벽이다. 열 번호가 $3k - 1$ 또는 $3k$인 칸, 즉 $2, 3, 5, 6, \ldots, 3M - 1, 3M$열의 칸에는 모두 색이 칠해져 있다($k = 1, 2, \ldots, M$). 색은 $26$가지이고 $1$번부터 $26$번까지 번호가 붙어 있다. 나머지 칸, 즉 $1, 4, 7, \ldots, 3M + 1$열의 칸에는 색이 칠해져 있지 않으며 모두 바닥이다.

이 판에서 다음 놀이를 한다. 먼저 $(2, 1)$에 말을 놓는다. 그다음 말을 인접한 바닥 칸으로 계속 옮긴다. 두 칸이 변을 맞대고 있으면 인접하다고 한다. 벽 칸이나 판 밖으로는 말을 옮길 수 없다. 목표는 말을 $(2, 3M + 1)$로 옮기는 것이다.

이 놀이에서는 마법 스위치 $26$개를 쓸 수 있다. 스위치에도 $1$번부터 $26$번까지 번호가 붙어 있고, $x$번 스위치는 $x$번 색에 대응한다. $x$번 스위치를 누르면 $x$번 색이 칠해진 바닥 칸은 모두 벽이 되고 $x$번 색이 칠해진 벽 칸은 모두 바닥이 된다. 두 변화는 동시에 일어난다.

스위치는 말을 움직이기 시작하기 전에만 누를 수 있다. 목표를 이룰 수 있게 하는 스위치 집합이 있는지 판정하고, 있으면 그런 집합 하나를 구하여라.

입력은 최대 $130$개의 데이터 집합으로 이루어진다. 각 데이터 집합의 첫 줄에는 정수 $M$($1 \le M \le 1000$)이 주어진다. 이어지는 세 줄에는 각각 $3M + 1$개의 문자가 주어지고, 이 세 줄이 판을 나타낸다. 그중 $i$번째 줄의 $j$번째 문자는 칸 $(i, j)$의 정보를 다음과 같이 나타낸다.

• $x$번째 대문자는 칸 $(i, j)$에 $x$번 색이 칠해져 있고 이 칸이 처음에 바닥이라는 뜻이다.
• $x$번째 소문자는 칸 $(i, j)$에 $x$번 색이 칠해져 있고 이 칸이 처음에 벽이라는 뜻이다.
• 마침표(.)는 칸 $(i, j)$에 색이 칠해져 있지 않다는 뜻이며, 이 칸은 바닥이다.

문자가 마침표인 것은 $j$가 $1, 4, 7, \ldots, 3M + 1$ 중 하나일 때, 그리고 그때뿐이다. 입력의 끝은 $0$ 하나만 있는 줄로 나타낸다.

각 데이터 집합마다 한 줄을 출력한다. 어떤 스위치 집합으로도 목표를 이룰 수 없으면 -1을 출력한다. 그렇지 않으면 누르는 스위치 집합을 다음 형식으로 출력한다.

n s1 s2 ... sn

$n$은 누르는 스위치의 개수이고, $s_1, s_2, \ldots, s_n$은 누르는 스위치에 대응하는 대문자다. $x$번째 대문자가 $x$번 스위치를 나타낸다. 누를 스위치가 하나도 없으면 $n = 0$이며, 이때는 $0$ 하나만 있는 줄을 출력한다.

목표를 이루는 스위치 집합은 여러 개일 수 있다. 그중 다음 방법으로 정한 집합 하나만 출력한다. $1$번 스위치부터 $26$번 스위치까지 차례로 누를지 정한다. 앞에서 정한 결정을 그대로 두고, 지금 보는 스위치를 누르지 않아도 뒤에 남은 스위치를 적절히 골라 목표를 이룰 수 있으면 누르지 않는다. 그런 방법이 없을 때만 누른다. 이렇게 정해진 대문자를 알파벳 순서로 공백 하나씩 띄어 출력한다.