시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
20 초 512 MB 19 6 3 21.429%

## 문제

You are given a rectangular board divided into square cells. The number of rows and columns in this board are $$3$$ and $$3 M + 1$$, respectively, where $$M$$ is a positive integer. The rows are numbered $$1$$ through $$3$$ from top to bottom, and the columns are numbered $$1$$ through $$3 M + 1$$ from left to right. The cell at the $$i$$-th row and the $$j$$-th column is denoted by $$(i, j)$$.

Each cell is either a floor cell or a wall cell. In addition, cells in columns $$2, 3, 5, 6, \ldots, 3 M - 1, 3 M$$ (numbers of form $$3 k - 1$$ or $$3 k$$, for $$k = 1, 2, \ldots, M$$) are painted in some color. There are $$26$$ colors which can be used for painting, and they are numbered $$1$$ through $$26$$. The other cells (in columns $$1, 4, 7, \ldots, 3 M + 1$$) are not painted and each of them is a floor cell.

You are going to play the following game. First, you put a token at cell $$(2, 1)$$. Then, you repeatedly move it to an adjacent floor cell. Two cells are considered adjacent if they share an edge. It is forbidden to move the token to a wall cell or out of the board. The objective of this game is to move the token to cell $$(2, 3 M + 1)$$.

For this game, $$26$$ magical switches are available for you! Switches are numbered $$1$$ through $$26$$ and each switch corresponds to the color with the same number. When you push switch $$x$$, each floor cell painted in color $$x$$ becomes a wall cell and each wall cell painted in color $$x$$ becomes a floor cell, simultaneously.

You are allowed to push some of the magical switches ONLY BEFORE you start moving the token. Determine whether there exists a set of switches to push such that you can achieve the objective of the game, and if there does, find such a set.

## 입력

$$The input is a sequence of at most \(130$$ datasets. Each dataset begins with a line containing an integer $$M$$ ($$1 \le M \le 1{,}000$$). The following three lines, each containing $$3 M + 1$$ characters, represent the board. The $$j$$-th character in the $$i$$-th of those lines describes the information of cell $$(i, j)$$, as follows:

• The $$x$$-th uppercase letter indicates that cell $$(i, j)$$ is painted in color $$x$$ and it is initially a floor cell.

• The $$x$$-th lowercase letter indicates that cell $$(i, j)$$ is painted in color $$x$$ and it is initially a wall cell.

• A period (.) indicates that cell $$(i, j)$$ is not painted and so it is a floor cell.

Here you can assume that $$j$$ will be one of $$1, 4, 7, \ldots, 3 M + 1$$ if and only if that character is a period. The end of the input is indicated by a line with a single zero.

## 출력

For each dataset, output $$-1$$ if you cannot achieve the objective. Otherwise, output the set of switches you push in order to achieve the objective, in the following format:

n s1 s2 ... sn

Here, $$n$$ is the number of switches you push and $$s_1, s_2, \ldots, s_n$$ are uppercase letters corresponding to switches you push, where the $$x$$-th uppercase letter denotes switch $$x$$. These uppercase letters $$s_1, s_2, \ldots, s_n$$ must be distinct, while the order of them does not matter. Note that it is allowed to output $$n = 0$$ (with no following uppercase letters) if you do not have to push any switches. See the sample output for clarification. If there are multiple solutions, output any one of them.

## 예제 입력 1

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.QB.QB.qb.
0


## 예제 출력 1

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