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