F. Five-Needle Telegraph
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For a Media Studies presentation on the history of telecommunication, Alice is going to use her skill in electronics to re-create the five-needle telegraph design. Unlike other communication systems, like the famous Morse telegraph system that succeeded it, the five-needle telegraph had the advantage of not requiring specialist training in order for its operators to send and receive messages.

Alice wants to create a generalized version, so we will actually describe the construction of an $$$n$$$-needle telegraph. Consider a square with $$$n$$$ rows and $$$n$$$ columns which has been rotated $$$45^\circ$$$, such that it now has $$$2n-1$$$ rows—so its first row contains $$$1$$$ entry, its second row contains $$$2$$$ entries, and so on, up until its $$$n$$$th row which contains $$$n$$$ entries; then, the $$$(n+1)$$$th row contains $$$n-1$$$ entries, the $$$(n+2)$$$th row contains $$$n-2$$$ entries, and so on, up until its final row has $$$1$$$ entry again.

The $$$n$$$th row contains a needle in each entry; each other square contains a single letter in each entry. You may refer to this diagram, taken from the Wikipedia page, for an $$$n$$$-needle telegraph with $$$n=5$$$.

Credits to user Dder

Each needle can be in one of $$$3$$$ states: it can be pointed vertically (its default state), it may be rotated $$$45^\circ$$$ counterclockwise (west of north), or it may be rotated $$$45^\circ$$$ clockwise (east of north). A valid message consists of choosing exactly two needles and rotating them in opposite directions (all other needles remain in the default state). The value of this message is equal to the letter that both rotated needles are pointing at. In the above diagram, the third needle has rotated $$$45^\circ$$$ clockwise, and the fifth needle has rotated $$$45^\circ$$$ counterclockwise, and so they point at the letter G

For this problem, you will be given the $$$n(n-1)$$$ letters on Alice's design of her telegraph, as well as $$$m$$$ needle configurations that correspond to valid messages. Please decode Alice's message!

Input

Input begins with a single line containing the integers and $$$n$$$ and $$$m$$$.

Then, $$$n-1$$$ lines of input follow, containing strings with $$$1, 2, 3, \dots, n-1$$$ letters each, respectively, corresponding to the letters in the first $$$n-1$$$ rows of the telegraph.

Then, $$$n-1$$$ lines of input follow, containing strings with $$$n-1, n-2, n-3, \dots, 1$$$ letters each, respectively, corresponding to the letters in the final $$$n-1$$$ rows of the telegraph.

Note that in general, the same letter may appear in multiple places in the telegraph.

Finally, $$$m$$$ lines of input follow, each containing a string of length $$$n$$$, describing Alice's messages in order. Exactly one character will be \ to represent the needle rotated $$$45^\circ$$$ counterclockwise, and exactly one other character will be / to represent the needle rotated $$$45^\circ$$$ clockwise; all other characters in each string are | to represent needles in their default state.

Output

Output a single line containing a string of length $$$m$$$, where the $$$i$$$th character of this string corresponds to the letter pointed at by the needles in the $$$i$$$th of Alice's messages.

Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 2 \leq n \leq 20 \\ 1 \leq m \leq 400 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{50} & n \leq 5 \\ \hline 2 & \mathbf{30} & \text{All needle configurations point to a letter in the top half.} \\ \hline 3 & \mathbf{20} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Example
Input
5 16
A
BD
EFG
HIKL
MNOP
RST
VW
Y
|\/||
||\/|
|/\||
|||\/
/\|||
/|||\
/||\|
/|||\
||/\|
||\/|
|/||\
/|||\
|||/\
||\/|
|\/||
||/|\
Output
NOIPHABAKODALONG
Note

The code ||/|\ corresponds to the needle configuration from the diagram in the problem statement.