MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 12px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

Problem Statement

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.

Input

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.

Output

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$ $s\_1$ $s\_2$ ... $s\_n$

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.

Sample Input

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```

### Output for the Sample Input

```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```

* * *

### Source Name

[JAG Practice Contest for ACM-ICPC Asia Regional 2013](http://acm-icpc.aitea.net/index.php?2013%2FPractice%2F%CC%CF%B5%BC%C3%CF%B6%E8%CD%BD%C1%AA)

* * *