旋转同色子序列

题目描述

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

对于每个 $i = 1, 2, \ldots, M$，按此顺序执行以下操作：

对 $S$ 中被染成颜色 $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$ 的每种颜色都至少有一个字符。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$S$
$C_1$ $C_2$ $\ldots$ $C_N$

输出格式

输出答案。

样例

8 3
apzbqrcs
1 2 3 1 2 2 1 2

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 1
aa
1 1

aa

数据范围

• $1 \le M \le N \le 2 \times 10^5$
• $1 \le C_i \le M$
• $N$、$M$、$C_i$ 均为整数。
• $S$ 是长度为 $N$、由小写英文字母组成的字符串。
• 对于每个整数 $1 \le i \le M$，存在整数 $1 \le j \le N$ 使得 $C_j = i$。