JKP 挑战赛

题目信息

时间限制: 1s

空间限制: 256M

输入文件: jkp.in

输出文件: jkp.out

题目描述

JKP(Jan-Ken Punch) 挑战赛是 JKP 村一年一度的盛会，JKP 村人才辈出，因此所谓的 JKP 挑战赛其实是村民们基于 Jan-Ken Punch 规则而考验快速计算能力的大赛。此次 JKP 大赛中请来了 $n$ 位志愿者，每位志愿者手持石头（用字符 A 表示）、剪刀（用字符 B）表示或布（用字符 C 表示）中的一个，$n$ 位志愿者根据手上持有的石头、剪刀或布可以用序列 $\{a_n\}$ 表示，$a_i$ 即为第 $i$ 位志愿者手持的物品（一个物品就是【一个石头】、【一个剪刀】或者【一个布】）。而挑战者需要完成多次形如 $[l, r]$ 的询问：

1. 挑战者手持给定物品（石头剪刀或布之一）从第 $l$ 位志愿者处出发
2. 挑战者与当前面对的志愿者进行一次 JKP 对战（其实就是石头剪刀布对战），若挑战者胜利，那么手持物品不变，否则挑战者将手持物品更改为当前面对的志愿者手持的物品
3. 挑战者走向下一位志愿者
4. 若挑战者移动到位置 $r+1$，则询问立即结束，挑战者向主办方汇报当前手持物品，否则回到步骤 2.

小 J 也决定参与此次 JKP 挑战赛，因此小 J 将面对如下格式的 $m$ 次询问：

• 修改询问：给出 $l, r, x, y$，表示 $[l, r]$ 中的所有志愿者若手持物品 x，则替换成物品 y；若手持物品 y，则替换成物品 x
• 挑战询问：给出 $l, r, x$，表示小 J 需要手持物品 x 经过 $[l, r]$，并向主办方汇报最终手持物品

请注意，挑战询问结束后，每个志愿者手上的物品会恢复原样，而修改询问会改变志愿者手上的物品。

输入格式

第一行两个数 $n, m$，含义如题所示

第二行一个长为 $n$，仅由 A, B, C 组成的字符串，含义如题所示

接下来 $m$ 行，每行第一个数为 $o p \in\{0,1\}$：

• 若 $o p=0$ 则表示一个修改询问 $l, r, x, y$
• 若 $o p=1$ 则表示一个挑战询问 $l, r, x$

其中 $1 \leq l \leq r \leq n$ 且 $x, y\in\{A, B, C\}$，所有数和字符用空格隔开

输出格式

对于每个挑战询问，输出一行表示小 J 最终手持物品对应的字符

样例

样例输入 1

6 8
AABAAC
0 2 4 A C
1 5 6 A
1 5 6 C
0 1 2 C A
1 2 5 C
1 1 3 A
0 2 4 B C
1 2 3 C

样例输出 1

C
C
A
B
C

数据范围与提示

• 对于所有数据，$1\leq n, m\leq 2\times 10^5$