String Decoding (APCS 2022-06 Intermediate)

There is a string encryption system. Each encryption uses a binary string \(e\) of length \(n\) to transform the current length-\(n\) string \(S\) into a new string \(T\). One encryption consists of two steps.

Step 1: Swap the two halves depending on the number of ones

If \(e\) contains an even number of ones, leave \(S\) unchanged.

If \(e\) contains an odd number of ones:

• When \(n\) is even, split \(S\) into equal-length strings \(L\) and \(R\), and change \(S=L+R\) into \(R+L\).
• When \(n\) is odd, write \(S\) as \(L+c+R\), where \(c\) is the middle character and \(L\) and \(R\) have equal length. Change it into \(R+c+L\). Thus, the middle character stays in the middle position.

Step 2: Take characters from the two ends

Start with an empty string \(T\), then read \(e\) from left to right:

• for a 0, remove the first character of the current \(S\) and append it to \(T\);
• for a 1, remove the last character of the current \(S\) and append it to \(T\).

After all of \(e\) has been read, every character of \(S\) has been removed, and the resulting \(T\) is the encrypted string.

There are \(m\) encryption tables \(e_1,e_2,\ldots,e_m\). The original string is first encrypted with \(e_1\), the result is encrypted with \(e_2\), and so on, ending with \(e_m\). The input gives only the final encrypted string. Recover and output the original string.

Input

The first line contains two integers \(m\) and \(n\): the number of encryption tables and the string length.

Each of the next \(m\) lines contains a binary string \(e_i\) of length \(n\), the \(i\)-th encryption table.

The last line contains a string of length \(n\) consisting only of uppercase English letters. It is the final encrypted string after all \(m\) tables have been applied in order.

Constraints

• \(1\le m,n\le100\)
• Every encryption table has exactly \(n\) characters and contains only 0 and 1.
• The encrypted string has exactly \(n\) characters and contains only A through Z.

Output

Output the decoded original string.

Scoring

Sample Input 1

1 5
10110
CABAD

Sample Output 1

BCAAD

Sample Explanation 1

The table 10110 contains three ones. Therefore, in Step 1, the original string BCAAD changes from BC + A + AD into AD + A + BC, namely ADABC.

Step 2 starts with S = ADABC and an empty T. Each column below shows the state after that character-removal operation has been completed:

After all five operations, S is empty and the encrypted string is CABAD. Undoing these operations recovers BCAAD.

Sample Input 2

3 6
111110
101101
000000
RETYWQ

Sample Output 2

QWERTY

Sample Explanation 2

The original string QWERTY becomes RETYWQ after the three tables are applied in order. Decoding must undo the tables in reverse order: 000000, 101101, and then 111110. This recovers QWERTY.

Source

APCS June 2022, Programming Task 2; ZeroJudge i400, String Decoding; explanation by Yi-Che Wang.