问题描述

给定一个由方块单元格组成的矩形棋盘。该棋盘的行数和列数分别为3和3M + 1，其中M是一个正整数。行从上到下编号为1到3，列从左到右编号为1到3M + 1。第(i, j)个单元格表示为$(i, j)$。

每个单元格要么是地板单元格，要么是墙单元格。另外，在第2、3、5、6、...、3M - 1、3M列（形如3k - 1或3k的数字，其中k = 1, 2, ... , M）中涂上了某种颜色。有26种可以用于绘制的颜色，它们以1到26进行编号。其他单元格（在第1、4、7、...、3M + 1列）未被涂色，每个都是地板单元格。

你要玩以下游戏。首先，你把一个令牌放在单元格(2, 1)上。然后，你反复将其移动到相邻的地板单元格上。如果两个单元格共享一个边，则被视为相邻。不允许将令牌移动到墙壁单元格或超出棋盘范围。游戏的目标是将令牌移动到单元格(2, 3M + 1)上。

对于这个游戏，你有26个魔法开关可供使用！开关编号为1到26，每个开关对应相同编号的颜色。当你按下开关x时，涂有颜色x的每个地板单元格都变成墙壁单元格，涂有颜色x的每个墙壁单元格都变成地板单元格，同时进行。

你只能在开始移动令牌之前按下其中一些魔法开关。确定是否存在一组开关可以按下以达到游戏的目标，如果存在，则找到这样一组开关。

输入

输入是一个由最多130个数据集组成的序列。每个数据集以包含一个整数M（$1 \le M \le 1,000$）的行开始。接下来的三行，每行包含$3M + 1$个字符，表示棋盘。其中第i行第j个字符描述了单元格$(i, j)$的信息，如下所示：

• 第x个大写字母表示单元格$(i, j)$被涂上颜色x，并且初始是地板单元格。
• 第x个小写字母表示单元格$(i, j)$被涂上颜色x，并且初始是墙单元格。
• 句点（.）表示单元格$(i, j)$未被涂色，因此是地板单元格。

在这里，你可以假设如果且仅当该字符是句点时，j将是$1, 4, 7, ..., 3M + 1$中的一个。输入的结束由一行只包含一个零表示。

输出

对于每个数据集，如果无法达到目标，请输出-1。否则，按照以下格式输出你按顺序按下的开关集合以实现目标：

$n$ $s\_1$ $s\_2$ ... $s\_n$

这里，$n$是你按下的开关数，$s\_1, s\_2, ..., s\_n$是对应于你按下的开关的大写字母，其中第x个大写字母表示开关x。这些大写字母$s\_1, s\_2, ..., s\_n$必须是不同的，但它们的顺序无关紧要。请注意，如果你不必按下任何开关，则允许输出$n = 0$（没有后面的大写字母）。有多个解决方案时，输出任何一个。

样例输入

3
.aa.cA.Cc.
.bb.Bb.AC.
.cc.ac.Ab.
1
.Xx.
.Yy.
.Zz.
6
.Aj.fA.aW.zA.Jf.Gz.
.gW.GW.Fw.ZJ.AG.JW.
.bZ.jZ.Ga.Fj.gF.Za.
9
.ab.gh.mn.st.yz.EF.KL.QR.WA.
.cd.ij.op.uv.AB.GH.MN.ST.XB.
.ef.kl.qr.wx.CD.IJ.OP.UV.yz.
2
.AC.Mo.
.IC.PC.
.oA.CM.
20
.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.qb.
.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.qb.
.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.QB.qb.
0```

**样例输出**

```plain
3 B C E
-1
3 J A G
10 A B G H M N S T Y Z
0
2 Q B```