시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 53 16 10 43.478%

문제

상근이는 문자열을 인코딩하는 흥미로운 아이디어를 가지고 있다. 다음은 인코딩이 동작하는 방법에 대한 설명이다.

인코딩하려고 하는 문자열의 각 문자를 x1, x2, ..., xn이라고 하자.

  1. 자연수 m과 집합 {1, 2, ..., n}에서 서로 다른 n개의 수 p1, p2, ... pn를 고른다. (p는 1부터 n까지 숫자의 순열이 된다)
  2. 3번을 m번 반복한다.
  3. 모든 1 ≤ i ≤ n 에 대해서, yi를 xpi로 정한다. 그 다음 xi와 yi를 바꾼다.

문자열 "hello"를 인코딩하려고 할 때를 생각해보자. m = 3를 고르고, 순열 p는 2, 3, 1, 5, 4를 고른다면, hello" -> "elhol" -> "lhelo" -> "helol"와 같이 인코딩 된다.

인코딩 된 문자열과 인코딩하는데 사용한 m과 p1, ..., pn이 주어졌을 때, 인코딩 하기 전 문자열을 구하는 프로그램을 작성하시오. (디코딩)

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n과 m이 주어진다. (1 ≤ n ≤ 80, 1 ≤ m ≤ 109) 다음 줄에는 인코딩하는데 사용한 n개의 서로 다른 숫자 p1, ..., pn이 주어진다. (1 ≤ pi ≤ n) 셋째 줄에는 인코딩된 문자열이 주어진다. 입력의 마지막 줄에는 0이 두 개 있다.

출력

각 테스트 케이스에 대해서 디코딩한 문자열을 출력한다.

예제 입력 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?
W3sicHJvYmxlbV9pZCI6IjY1MDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWM1ZjQgXHViNTE0XHVjZjU0XHViNTI5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1Yzc3OFx1Y2Y1NFx1YjUyOVx1ZDU1OFx1YjI5NCBcdWQ3NjVcdWJiZjhcdWI4NWNcdWM2YjQgXHVjNTQ0XHVjNzc0XHViNTE0XHVjNWI0XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YjJlNFx1Yzc0Y1x1Yzc0MCBcdWM3NzhcdWNmNTRcdWI1MjlcdWM3NzQgXHViM2Q5XHVjNzkxXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjMTI0XHViYTg1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzhcdWNmNTRcdWI1MjlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFjMDEgXHViYjM4XHVjNzkwXHViOTdjIHg8c3ViPjE8XC9zdWI+LCB4PHN1Yj4yPFwvc3ViPiwgLi4uLCB4PHN1Yj5uPFwvc3ViPlx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVjNzkwXHVjNWYwXHVjMjE4IG1cdWFjZmMgXHVjOWQxXHVkNTY5IHsxLCAyLCAuLi4sIG59XHVjNWQwXHVjMTFjIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5Nzggblx1YWMxY1x1Yzc1OCBcdWMyMTggcDxzdWI+MTxcL3N1Yj4sIHA8c3ViPjI8XC9zdWI+LCAuLi4gcDxzdWI+bjxcL3N1Yj5cdWI5N2MgXHVhY2UwXHViOTc4XHViMmU0LiAocFx1YjI5NCAxXHViZDgwXHVkMTMwIG5cdWFlNGNcdWM5YzAgXHVjMjJiXHVjNzkwXHVjNzU4IFx1YzIxY1x1YzVmNFx1Yzc3NCBcdWI0MWNcdWIyZTQpPFwvbGk+XHJcblx0PGxpPjNcdWJjODhcdWM3NDQgbVx1YmM4OCBcdWJjMThcdWJjZjVcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCAxICZsZTsgaSAmbGU7IG4gXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgeTxzdWI+aTxcL3N1Yj5cdWI5N2MgeDxzdWI+cGk8XC9zdWI+XHViODVjIFx1YzgxNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyB4PHN1Yj5pPFwvc3ViPlx1YzY0MCB5PHN1Yj5pPFwvc3ViPlx1Yjk3YyBcdWJjMTRcdWFmYmNcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHViYjM4XHVjNzkwXHVjNWY0ICZxdW90O2hlbGxvJnF1b3Q7XHViOTdjIFx1Yzc3OFx1Y2Y1NFx1YjUyOVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NjAgXHViNTRjXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC4gbSA9IDNcdWI5N2MgXHVhY2UwXHViOTc0XHVhY2UwLCBcdWMyMWNcdWM1ZjQgcFx1YjI5NCAyLCAzLCAxLCA1LCA0XHViOTdjIFx1YWNlMFx1Yjk3OFx1YjJlNFx1YmE3NCwgaGVsbG8mcXVvdDsgLSZndDsgJnF1b3Q7ZWxob2wmcXVvdDsgLSZndDsgJnF1b3Q7bGhlbG8mcXVvdDsgLSZndDsgJnF1b3Q7aGVsb2wmcXVvdDtcdWM2NDAgXHVhYzE5XHVjNzc0IFx1Yzc3OFx1Y2Y1NFx1YjUyOSBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3OFx1Y2Y1NFx1YjUyOSBcdWI0MWMgXHViYjM4XHVjNzkwXHVjNWY0XHVhY2ZjIFx1Yzc3OFx1Y2Y1NFx1YjUyOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWMwYWNcdWM2YTlcdWQ1NWMgbVx1YWNmYyBwMSwgLi4uLCBwblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzhcdWNmNTRcdWI1MjkgXHVkNTU4XHVhZTMwIFx1YzgwNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIChcdWI1MTRcdWNmNTRcdWI1MjkpPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgblx1YWNmYyBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgODAsIDEgJmxlOyBtICZsZTsgMTA8c3VwPjk8XC9zdXA+KSBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc3OFx1Y2Y1NFx1YjUyOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWMwYWNcdWM2YTlcdWQ1NWMgblx1YWMxY1x1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzIyYlx1Yzc5MCBwPHN1Yj4xPFwvc3ViPiwgLi4uLCBwPHN1Yj5uPFwvc3ViPlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgcDxzdWI+aTxcL3N1Yj4gJmxlOyBuKSBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc3OFx1Y2Y1NFx1YjUyOVx1YjQxYyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWI1MTRcdWNmNTRcdWI1MjlcdWQ1NWMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2NTA1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGVjb2RlIHRoZSBTdHJpbmdzIiwiZGVzY3JpcHRpb24iOiI8cD5CcnVjZSBGb3JjZSBoYXMgaGFkIGFuIGludGVyZXN0aW5nIGlkZWEgaG93IHRvIGVuY29kZSBzdHJpbmdzLiBUaGUgZm9sbG93aW5nIGlzIHRoZSBkZXNjcmlwdGlvbiBvZiBob3cgdGhlIGVuY29kaW5nIGlzIGRvbmU6PFwvcD5cclxuXHJcbjxwPkxldCB4PHN1Yj4xPFwvc3ViPix4PHN1Yj4yPFwvc3ViPiwuLi4seDxzdWI+bjxcL3N1Yj4gYmUgdGhlIHNlcXVlbmNlIG9mIGNoYXJhY3RlcnMgb2YgdGhlIHN0cmluZyB0byBiZSBlbmNvZGVkLjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkNob29zZSBhbiBpbnRlZ2VyIG0gYW5kIG4gcGFpcndpc2UgZGlzdGluY3QgbnVtYmVycyBwPHN1Yj4xPFwvc3ViPixwPHN1Yj4yPFwvc3ViPiwuLi4scDxzdWI+bjxcL3N1Yj4gZnJvbSB0aGUgc2V0IHsxLCAyLCAuLi4sIG59IChhIHBlcm11dGF0aW9uIG9mIHRoZSBudW1iZXJzIDEgdG8gbikuPFwvbGk+XHJcblx0PGxpPlJlcGVhdCB0aGUgZm9sbG93aW5nIHN0ZXAgbSB0aW1lcy48XC9saT5cclxuXHQ8bGk+Rm9yIDEgJmxlOyBpICZsZTsgbiBzZXQgeTxzdWI+aTxcL3N1Yj4gdG8geDxzdWI+cGk8XC9zdWI+LCBhbmQgdGhlbiBmb3IgMSAmbGU7IGkgJmxlOyBuIHJlcGxhY2UgeDxzdWI+aTxcL3N1Yj4gYnkgeTxzdWI+aTxcL3N1Yj4uPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHdoZW4gd2Ugd2FudCB0byBlbmNvZGUgdGhlIHN0cmluZyAmcXVvdDtoZWxsbyZxdW90OywgYW5kIHdlIGNob29zZSB0aGUgdmFsdWUgbSA9IDMgYW5kIHRoZSBwZXJtdXRhdGlvbiAyLCAzLCAxLCA1LCA0LCB0aGUgZGF0YSB3b3VsZCBiZSBlbmNvZGVkIGluIDMgc3RlcHM6ICZxdW90O2hlbGxvJnF1b3Q7IC0mZ3Q7ICZxdW90O2VsaG9sJnF1b3Q7IC0mZ3Q7ICZxdW90O2xoZWxvJnF1b3Q7IC0mZ3Q7ICZxdW90O2hlbG9sJnF1b3Q7LjxcL3A+XHJcblxyXG48cD5CcnVjZSBnaXZlcyB5b3UgdGhlIGVuY29kZWQgc3RyaW5ncywgYW5kIHRoZSBudW1iZXJzIG0gYW5kIHA8c3ViPjE8XC9zdWI+LCAuLi4sIHA8c3ViPm48XC9zdWI+IHVzZWQgdG8gZW5jb2RlIHRoZXNlIHN0cmluZ3MuIEhlIGNsYWltcyB0aGF0IGJlY2F1c2UgaGUgdXNlZCBodWdlIG51bWJlcnMgbSBmb3IgZW5jb2RpbmcsIHlvdSB3aWxsIG5lZWQgYSBsb3Qgb2YgdGltZSB0byBkZWNvZGUgdGhlIHN0cmluZ3MuIENhbiB5b3UgZGlzcHJvdmUgdGhpcyBjbGFpbSBieSBxdWlja2x5IGRlY29kaW5nIHRoZSBzdHJpbmdzPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdHdvIG51bWJlcnMgbiBhbmQgbSAoMSAmbGU7IG4gJmxlOyA4MCwgMSAmbGU7IG0gJmxlOyAxMDxzdXA+OTxcL3N1cD4pLiBUaGUgZm9sbG93aW5nIGxpbmUgY29uc2lzdHMgb2YgbiBwYWlyd2lzZSBkaWZmZXJlbnQgbnVtYmVycyBwPHN1Yj4xPFwvc3ViPiwuLi4scDxzdWI+bjxcL3N1Yj4gKDEgJmxlOyBwPHN1Yj5pPFwvc3ViPiAmbGU7IG4pLiBUaGUgdGhpcmQgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBleGFjdGx5IG4gY2hhcmFjdGVycywgYW5kIHJlcHJlc2VudCB0aGUgZW5jb2RlZCBzdHJpbmcuIFRoZSBsYXN0IHRlc3QgY2FzZSBpcyBmb2xsb3dlZCBieSBhIGxpbmUgY29udGFpbmluZyB0d28gemVyb3M8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCBvbmUgbGluZSB3aXRoIHRoZSBkZWNvZGVkIHN0cmluZy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=