PDECODE  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_{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?
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^{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.
Output
For each test case, print one line with the decoded string.
Example
Input: 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 Output: hello second test case encoded?
hide comments
madhur4127:
20180319 10:55:07
no inversion, just permutation matrix and hardest part was to input string with whitespace. cin.ignore() did the job. 

Deepak Gupta:
20141011 14:00:43
Use gets() twice to read string, to avoid new line issues 

Somnath Singh :D:
20110831 14:46:33
Contruct the Symmetry group , tht's will give u the idea to do ... with O(nlog) .


Adrian Kuegel:
20100817 09:21:39
I think your algorithm is O(m * n), which is of course too slow. It is possible to solve this problem in O(n) or in O(n log m). 

Adrian Kuegel:
20100416 08:56:52
no 

nishaanth:
20100410 15:46:37
has it to do with number of inversions?? 
Added by:  Adrian Kuegel 
Date:  20080712 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  University of Ulm Local Contest 2008 