/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
英小文字からなる長さ N の文字列 S が与えられます。 S の各文字は色 1 、色 2 、\ldots 、色 M の M 色のうちのいずれかで塗られており、 i = 1, 2, \ldots, N について、S の i 文字目は色 C_i で塗られています。
各 i = 1, 2, \ldots, M について、この順番に下記の操作を行います。
- S の色 i で塗られた文字からなる部分を、右に 1 つ巡回シフトする。 すなわち、S の 色 i で塗られた文字の位置が先頭のものから順に p_1, p_2, p_3, \ldots, p_k 文字目であるとき、 S の p_1, p_2, p_3, \ldots, p_k 文字目を、それぞれ、S の p_k, p_1,p_2, \ldots, p_{k-1} 文字目で同時に置き換える。
上記の操作をすべて行った後の、最終的な S を出力してください。
なお、M 色あるどの色についても、その色で塗られた S の文字が必ず 1 つ以上存在することが、制約として保証されます。
制約
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq C_i \leq M
- N, M, C_i はすべて整数
- S は英小文字からなる長さ N の文字列
- 任意の整数 1 \leq i \leq M に対して、ある整数 1 \leq j \leq N が存在して C_j = i が成り立つ
入力
入力は以下の形式で標準入力から与えられる。
N M S C_1 C_2 \ldots C_N
出力
答えを出力せよ。
入力例 1
8 3 apzbqrcs 1 2 3 1 2 2 1 2
出力例 1
cszapqbr
はじめ、S = apzbqrcs です。
- i = 1 に対する操作では、S の 1, 4, 7 文字目からなる部分を右に 1 つ巡回シフトします。その結果、S =
cpzaqrbsとなります。 - i = 2 に対する操作では、S の 2, 5, 6, 8 文字目からなる部分を右に 1 つ巡回シフトします。その結果、S =
cszapqbrとなります。 - i = 3 に対する操作では、S の 3 文字目からなる部分を右に 1 つ巡回シフトします。その結果、S =
cszapqbrとなります（操作の前後で S は変わりません）。
よって、最終的な S である cszapqbr を出力します。
入力例 2
2 1 aa 1 1
出力例 2
aa
Score : 300 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters. Each character of S is painted in one of the M colors: color 1, color 2, ..., color M; for each i = 1, 2, \ldots, N, the i-th character of S is painted in color C_i.
For each i = 1, 2, \ldots, M in this order, let us perform the following operation.
- Perform a right circular shift by 1 on the part of S painted in color i. That is, if the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters are painted in color i from left to right, then simultaneously replace the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters of S with the p_k-th, p_1-th, p_2-th, \ldots, p_{k-1}-th characters of S, respectively.
Print the final S after the above operations.
The constraints guarantee that at least one character of S is painted in each of the M colors.
Constraints
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq C_i \leq M
- N, M, and C_i are all integers.
- S is a string of length N consisting of lowercase English letters.
- For each integer 1 \leq i \leq M, there is an integer 1 \leq j \leq N such that C_j = i.
Input
The input is given from Standard Input in the following format:
N M S C_1 C_2 \ldots C_N
Output
Print the answer.
Sample Input 1
8 3 apzbqrcs 1 2 3 1 2 2 1 2
Sample Output 1
cszapqbr
Initially, S = apzbqrcs.
- For i = 1, perform a right circular shift by 1 on the part of S formed by the 1-st, 4-th, 7-th characters, resulting in S =
cpzaqrbs. - For i = 2, perform a right circular shift by 1 on the part of S formed by the 2-nd, 5-th, 6-th, 8-th characters, resulting in S =
cszapqbr. - For i = 3, perform a right circular shift by 1 on the part of S formed by the 3-rd character, resulting in S =
cszapqbr(here, S is not changed).
Thus, you should print cszapqbr, the final S.
Sample Input 2
2 1 aa 1 1
Sample Output 2
aa