Repeated Permutation Cipher

Interview

Time limit1sMemory limit128 MB

Summary

Given a permutation key and a repeat count k, apply the permutation to each padded message k times and print the result.

Level: Medium5 of 10
Topics: Array, Implementation, Math, Simulation
Solved: No attempts yet

Problem

Bob and Alice began using a brand-new encryption scheme. It is not a public-key cryptosystem; instead it relies on a secret key known only to the two of them.

The secret key is a sequence of $n$ distinct integers $a_1, a_2, \dots, a_n$ , each greater than $0$ and at most $n$ . In other words, $a$ is a permutation of $1$ through $n$ .

Encryption works as follows. Write the message under the key so that each character of the message lines up with a number of the key. The character at position $i$ in the message is moved to position $a_i$ in the encrypted message. The resulting text is then encrypted again in the same way, and this is repeated a total of $k$ times. After the $k$ -th encryption the result is exchanged.

The length of the message is always at most $n$ . If the message is shorter than $n$ , spaces are appended to its end so that its length becomes exactly $n$ .

Given the key and several pairs of a repeat count $k$ and a message, write a program that outputs each message after it has been encrypted $k$ times.

Input

The input consists of several blocks.

The first line of each block contains an integer $n$ ( $0 < n \le 200$ ). The next line contains the key: $n$ integers, pairwise distinct and each between $1$ and $n$ , separated by spaces. The following lines each contain an integer $k$ and a message of ASCII characters, separated by a single space. Each line ends with an end-of-line character, which is not part of the message. A block ends with a line containing only the number $0$ .

After the last block, a separate line containing only the number $0$ marks the end of the input.

$k$ may be very large.

Output

For each (repeat count, message) pair, print the encrypted message on its own line. Every printed line has exactly $n$ characters, preserving any trailing spaces of the padded message. The results of the blocks are printed in the order they appear in the input, with no blank line between blocks.

Examples4

Example 1

Input

10
4 5 3 7 2 8 1 6 10 9
1 Hello Bob
1995 CERC
0
0

Expected output

BolHeol  b
C RCE

Example 2
Input
```
5
1 2 3 4 5
7 abc
0
0
```
Expected output
```
abc  
```
Example 3
Input
```
2
2 1
1 AB
0
0
```
Expected output
```
BA
```
Example 4
Input
```
2
2 1
2 AB
0
0
```
Expected output
```
AB
```