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 x1, x2 ... xn be the sequence of characters of the string to be encoded.

  1. Choose an integer m and n pairwise distinct numbers p1,p2 ... pn 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 yi to xpi, and then for 1 ≤ i ≤ n replace xi by yi.

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 p1 ... pn 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 ≤ 109). The following line consists of n pairwise different numbers p1 ... pn (1 ≤ pin). 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?

Added by:Adrian Kuegel
Date:2008-07-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:University of Ulm Local Contest 2008

hide comments
2018-03-19 10:55:07
no inversion, just permutation matrix and hardest part was to input string with whitespace. cin.ignore() did the job.
2014-10-11 14:00:43 Deepak Gupta
Use gets() twice to read string, to avoid new line issues
2011-08-31 14:46:33 Somnath Singh :D
Contruct the Symmetry group , tht's will give u the idea to do ... with O(nlog) .
2010-08-17 09:21:39 Adrian Kuegel
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).
2010-04-16 08:56:52 Adrian Kuegel
no
2010-04-10 15:46:37 nishaanth
has it to do with number of inversions??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.