C. Cellular Automaton
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Loureiro is fond of observing and creating patterns. One day, he discovered a device, named unidimensional cellular automaton. Observing his operation, Loureiro found out that this device receives an equally divided tape of size $$$N$$$ as input, numbered from $$$1$$$ to $$$N$$$, where each cell is either a digit $$$0$$$ or $$$1$$$, and outputs a new tape of the same size. The device works as follow: for each position we take the number formed by the binary representation of $$$s_i$$$ concatenated with its neighbours $$$(s_{i-1}s_{i}s_{i+1})$$$, consider the tape is circular $$$(s_{0} = s_{N})$$$. From a set of rules defined by the device, this number could produce a cell with digit $$$0$$$ or $$$1$$$ for the resulting tape on position $$$i$$$.

Loureiro made modifications on this machine, now he can regulate its set of rules, defined as:

  • $$$K$$$ : The size of the neighborhood (originally $$$1$$$), that defines the number of cells to the left and to the right to be analyzed.
  • $$$M$$$ : A binary number with $$$(2^{2*k+1})$$$ bits, where the $$$i$$$th bit defines the mapping for number $$$i$$$.

For example, if $$$K = 1$$$ and $$$M = 00011110$$$ we have the following correspondence:

Loureiro has a tape, and after adjusting the device, he wonders what would be the final state of the tape after passing it $$$Q$$$ times on the machine. As Loureiro is very lazy, he asked you to finish this task.

Input

The first line contains 3 integers $$$N$$$, $$$K$$$ and $$$Q$$$, $$$(1 \leq N \leq 1000, 1 \leq K \leq 5, 1 \leq Q \leq 100)$$$, representing the tape size, neighborhood size and the amount of repetitions respectively. It's guaranteed that $$$2*K+1 \leq N$$$. The second line contains a binary string $$$m$$$ of size $$$2^{2*k+1}$$$, the mapping of the rule set. The third line has a binary string $$$s$$$ of size $$$N$$$, representing the tapes's initial state.

Output

A binary string representing the final state of the tape after $$$Q$$$ repetitions.

Examples
Input
11 1 1
00011110
00000100000
Output
00001110000
Input
15 1 25
01101110
010110101100101
Output
011000011111010
Input
12 2 42
00000000000000000000000000011110
111010001011
Output
000000000110
Input
12 2 23
11000101010001001001011101001100
010011111001
Output
101010101010