시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 18 6 6 54.545%

문제

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

인코딩하려고 하는 문자열의 각 문자를 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이 두 개 있다.

출력

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

예제 입력

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

예제 출력

hello
second test case
encoded?

힌트