Magical Switches

You are given a rectangular board divided into square cells. It has $3$ rows and $3M + 1$ columns, where $M$ is a positive integer. Rows are numbered $1$ through $3$ from top to bottom, and columns are numbered $1$ through $3M + 1$ from left to right. The cell in row $i$ and column $j$ is written $(i, j)$.

Every cell is either a floor cell or a wall cell. The cells whose column number is $3k - 1$ or $3k$, that is the cells in columns $2, 3, 5, 6, \ldots, 3M - 1, 3M$, are all painted in some color ($k = 1, 2, \ldots, M$). There are $26$ colors, numbered $1$ through $26$. The other cells, those in columns $1, 4, 7, \ldots, 3M + 1$, are not painted and all of them are floor cells.

You play the following game on the board. First you put a token on cell $(2, 1)$. Then you repeatedly move it to an adjacent floor cell. Two cells are adjacent when they share an edge. You cannot move the token to a wall cell or off the board. The objective is to move the token to cell $(2, 3M + 1)$.

For this game you have $26$ magical switches. Switches are numbered $1$ through $26$, and switch $x$ corresponds to the color with the same number. When you push switch $x$, every floor cell painted in color $x$ becomes a wall cell and every wall cell painted in color $x$ becomes a floor cell, both at the same time.

You may push switches only before the token starts moving. Decide whether a set of switches that achieves the objective exists, and if it does, find one such set.

The input holds at most $130$ datasets. The first line of each dataset contains an integer $M$ ($1 \le M \le 1000$). The next three lines contain $3M + 1$ characters each and describe the board. The $j$-th character of the $i$-th of those lines describes cell $(i, j)$ as follows.

• The $x$-th uppercase letter means that cell $(i, j)$ is painted in color $x$ and is initially a floor cell.
• The $x$-th lowercase letter means that cell $(i, j)$ is painted in color $x$ and is initially a wall cell.
• A period (.) means that cell $(i, j)$ is not painted, so it is a floor cell.

A character is a period when $j$ is one of $1, 4, 7, \ldots, 3M + 1$, and only then. The end of the input is a line holding a single zero.

Print one line for each dataset. If no set of switches achieves the objective, print -1. Otherwise print the set of switches you push 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 the uppercase letters of those switches, where the $x$-th uppercase letter denotes switch $x$. If you push no switch then $n = 0$, and the line holds a single $0$.

Several sets of switches can achieve the objective. Print only the one set determined as follows. Decide switches $1$ through $26$ in this order. Keeping the decisions already made, leave the current switch unpushed if the objective can still be achieved by some choice of the switches after it, and push it only when no such choice exists. Print the chosen uppercase letters in alphabetical order, separated by single spaces.