Word Maker (APCS 2023-01 Intermediate)

You are given a lowercase English string \(S\) of length \(K\). The word-making program rearranges its characters according to a permutation \(P_1,P_2,\ldots,P_K\) of the integers from \(1\) to \(K\).

In one operation, the character at position \(i\) of the old string is copied to position \(P_i\) of the new string. In other words,

Since \(P\) is a permutation, every position in the new string receives exactly one character. After an operation, the new string becomes the old string for the next operation.

The following diagram applies the permutation \((4,1,3,2)\) to abac. The characters at old positions \(1,2,3,4\) move to new positions \(4,1,3,2\), respectively, producing bcaa.

The program performs \(Q\) operations in order, each with a new permutation. Given \(R\), report the first \(R\) positions separately. Output one line for each position \(j\): concatenate the characters at position \(j\) after operations \(1,2,\ldots,Q\), in that order.

Input

The first line contains three integers \(K,Q,R\).

The second line contains the lowercase string \(S\) of length \(K\).

Each of the next \(Q\) lines contains \(K\) integers \(P_1,P_2,\ldots,P_K\), the permutation used by that operation.

Constraints

• \(1\le R\le K\le 20\)
• \(1\le Q\le 20\)
• \(S\) contains only lowercase English letters.
• For every operation, \(P_1,P_2,\ldots,P_K\) is a permutation of the integers from \(1\) to \(K\).

Output

Output \(R\) lines.

Line \(j\) must contain a string of length \(Q\): the characters at position \(j\) after each operation, in chronological order.

Scoring

There are two subtasks:

Sample Input 1

5 4 1
abcde
2 1 3 5 4
5 1 2 4 3
4 1 2 3 5
3 1 4 5 2

Sample Output 1

bacd

Sample Explanation 1

The strings after the four operations are baced, acdeb, cdeab, and dbcea. Since \(R=1\), only the first character is recorded after each operation. These characters are b, a, c, and d, so the output is bacd.

Sample Input 2

4 3 4
abac
4 1 3 2
1 2 3 4
2 3 4 1

Sample Output 2

bba
ccb
aac
aaa

Sample Explanation 2

The strings after the three operations are bcaa, bcaa, and abca. Reading each of the four positions through these three states gives the output lines bba, ccb, aac, and aaa.

Source

2023 January APCS Programming Practice, Problem 2: ZeroJudge j606, Word Maker. The presentation and sample explanations also refer to Yi-Zhe Wang's HackMD solution.