PDECODE - Decode the Strings

题意翻译

给出n个字符交换方式与置换m次后的最终置换结果,要求还原出置换前字符串,如hello置换方式2,3,1,5,4;置换一次后为elhol; 输入多组数据每组数据首行为n,m如题所述,第二行为n个字符表示第i个字符的置换方式,第三行为置换后字符串,输入最后以0,0结尾。 输出置换前字符串

题目描述

Bruce Force has had an interesting idea how to encode strings. The following is the description of how the encoding is done: Let x $ _{1} $ ,x $ _{2} $ ,...,x $ _{n} $ be the sequence of characters of the string to be encoded. 1. Choose an integer _m_ and _n_ pairwise distinct numbers p $ _{1} $ ,p $ _{2} $ ,...,p $ _{n} $ from the set {_1_, _2_, ..., _n_} (a permutation of the numbers _1_ to _n_). 2. Repeat the following step _m_ times. 3. 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 $ _{1} $ , ..., 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?

输入输出格式

输入格式


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 $ ^{9} $_ ). The following line consists of _n_ pairwise different numbers p $ _{1} $ ,...,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.

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

hello
second test case
encoded?