103142: [Atcoder]ABC314 C - Rotate Colored Subsequence

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

问题描述

给你一个长度为 N 的字符串 S，由小写英文字母组成。 字符串 S 中的每个字符都被涂成了 $M$ 种颜色之一：颜色 1，颜色 2，...，颜色 $M$；对于 $i = 1, 2, \ldots, N$，字符串 S 的第 $i$ 个字符被涂成颜色 $C_i$。

按照以下顺序，对每种颜色执行以下操作。

• 将涂成颜色 $i$ 的部分向右循环移位 1 位。 即，如果从左到右第 $p_1$ 个，$p_2$ 个，$p_3$ 个，$\ldots$，$p_k$ 个字符被涂成颜色 $i$，则同时将字符串 S 的第 $p_1$ 个，$p_2$ 个，$p_3$ 个，$\ldots$，$p_k$ 个字符替换为字符串 S 的第 $p_k$ 个，$p_1$ 个，$p_2$ 个，$\ldots$，$p_{k-1}$ 个字符。

输出执行上述操作后的最终字符串 S。

约束条件保证了字符串 S 中至少有一个字符被涂成了每种颜色。

约束

• $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 没有改变）。

因此，你应该输出 cszapqbr，即最终的字符串 S。

样例输入 2

2 1
aa
1 1

样例输出 2

aa