bee 1644 - Decode the Strings

Bruce Force has had an interesting idea how to encode strings. The following is the description of how the encoding is done:

Let x₁,x₂,...,x_n be the sequence of characters of the string to be encoded.

Choose an integer M and N pairwise distinct numbers p₁,p₂,...,p_n from the set {1, 2, ..., N} (a permutation of the numbers 1 to N).
Repeat the following step m times.
For 1 ≤ i ≤ N set y_i to x_pi, and then for 1 ≤ i ≤ N replace x_i by y_i.

For example, when we want to encode the string "hello", and we choose the value M = 3 and the permutation 2, 3, 1, 5, 4, the data would be encoded in 3 steps: "hello" -> "elhol" -> "lhelo" -> "helol".

Bruce gives you the encoded strings, and the numbers M and p₁, ..., p_n used to encode these strings. He claims that because he used huge numbers m for encoding, you will need a lot of time to decode the strings. Can you disprove this claim by quickly decoding the strings?

Input

The input contains several test cases. Each test case starts with a line containing two numbers N and M (1 ≤ N ≤ 80, 1 ≤ M ≤ 10⁹). The following line consists of N pairwise different numbers p₁,...,p_n (1 ≤ p_i ≤ N). The third line of each test case consists of exactly N characters, and represent the encoded string. The last test case is followed by a line containing two zeros.

Output

For each test case, print one line with the decoded string.

Sample Input	Sample Output
5 3 2 3 1 5 4 helol 16 804289384 13 10 2 7 8 1 16 12 15 6 5 14 3 4 11 9 scssoet tcaede n 8 12 5 3 4 2 1 8 6 7 encoded? 0 0	hello second test case encoded?