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.

- 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*). - 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_{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 ≤ 109). The following line consists of n pairwise different numbers p1,...,pn (1 ≤ pi ≤ 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.

提交代码