Jesse is a biologist and he was studying some aspects of life when he discovered that certain
species of sea animals tried to tell him some things about God. Those animals were using a certain
language to speak with him. They wrote down in binary code (black and white) in the shell they have.
As Jesse was the only one that this message was intended to be delivered, they encrypted the message
in such way that there is a rule to decrypt every bit in the spherical-shaped shell looking at 3 other bit:
the left, itself and the right in this order. So first they write the cyphered message and the rule to
decrypt it in lexicographical order, so the rule space in the shell containing the bit to decrypt “101” will
be rule's bit 5. To turn the cryptography more elaborated there is also the number of rounds that this
must be done to the entire message. Jesse wants to hire you to write a program for him to decrypt the
text and live in harmony forever and ever with the animals he loves and find out who is and what this
God wants to do.

Input

The input has several test cases. The first line of a test case contains the message length L (0 < L ≤
10000). The next line contains the message M, of length L bits. In the next line, your program should
read the 8-bits rule R. In another line, the number of rounds 0 ≤ N ≤ 10000. Your program must read
until the end of file.

Output

For each test case your program must write the message M after applying the rule R for N rounds.

Example

Input:
5
10111
10101010
1
10
1011010101
11100010
2
Output:
10000
1011010101