新冬夜愚戏之歌（nwnfps）

题目背景

「少女」没有做出冬夜愚戏之歌这道题目，于是出了一道新冬夜愚戏之歌来慰藉自己。

题目描述

「少女」每次听到同事的谈话，总会认为：「公鸡」和「木偶」意见不同，「公鸡」总是对的，「木偶」和「仆人」意见不同，「木偶」总是对的，「仆人」和「公鸡」意见不同，「仆人」总是对的。

回到月亮上之后，在记忆之中，她有这么一段只有「公鸡」，「木偶」，「仆人」谈话的序列，可以记「公鸡」的谈话为 G，「木偶」的谈话为 M，「仆人」的谈话为 P。经过不仔细思考之后，「少女」每次会将这个谈话序列转化为另一个谈话序列，具体来说：

• 设上一个谈话序列为 $s$，转化后的谈话序列为 $t$，初始 $t$ 为空。
• 依次将 $s$ 中从前往后相邻的人拿出来（例如 $(s_1, s_2), (s_2, s_3), ... (s_{|s| - 1}, s_{|s|})$），看看哪个人说的话总是对的，将这个人的谈话加入 $t$ 中，当然如果是一样的人，那么将这个人加入 $t$。

假设初始的谈话序列为 $st$，那么「少女」经过 $|st| - 1$ 次不仔细思考后，谈话序列的长度会变成 $1$，她会认为这个人是 $st$ 谈话序列的胜利者，即这个人说的话在本次谈话中总是对的！

某一次执行官们的茶会，他们三个人又开始了一些争论，记从始至终的谈话序列为 $str$，那么「少女」会有序进行一些操作：

• 1 l r，「少女」从第 $l$ 个人谈话的时候开始倾听，到第 $r$ 个人谈话的时候又开始睡觉，她想知道这一段区间到底谁说的话总是对的。即取出 $str[l, r]$，判断其谁说的话总是对的。
• 2 x k，「少女」意识到在第 $x$ 个时间段谈话的人不是原来的那个，而是 $k$ 这个人。即将 $str_x$ 修改为字符 $k$。

由于她还要闭着眼睛睡觉，所以请你帮助她解决这些问题。

然而，上述中“人”泛指提瓦特大陆物种，因为众所周知，「公鸡」是妖精。

【一些说明】

用更加形式化的语言来说，相邻两个字符比较时，G, M 会保留 G。M, P 会保留 M。G, P 会保留 P。

对于一个序列操作的具体例子，【提示说明】里会讲到。

输入格式

从文件 $\bm{nwnfps.in}$ 中读入数据。

「少女」说因为冬夜愚戏之歌有多测，所以本题也有 $t$ 组数据。

为了方便你的答题，第一行输入会给出测试点编号 $c$ 和测试数据组数 $t$。

接下来对于每组数据，第一行输入 $n, m$，表示最初谈话序列的长度以及她进行的操作数 $m$。

第二行输入 $str$，表示最初谈话序列。

接下来 $m$ 行，每行输入一个满足描述中操作格式的操作。

输出格式

输出到文件 $\bm{nwnfps.out}$ 中。

对于每组数据，输出若干行，每一行输出一个数表示对应的 $1$ 操作获得的答案。

输入输出样例 #1

输入 #1

0 2
3 3
GMP
1 1 3
2 2 P
1 1 3
6 6
GGMPPM
1 2 5
2 3 P
1 1 6
2 4 G
1 3 6
2 2 M

输出 #1

G
P
G
M
M

输入输出样例 #2

输入 #2

0 2
5 5
GMPGP
1 1 5
2 3 M
1 2 4
2 1 P
1 1 3
10 10
GGMPPMPMGG
1 3 7
2 5 M
1 1 5
2 8 P
1 2 8
2 3 G
1 4 10
2 6 G
1 5 9
1 1 10

输出 #2

G
G
M
M
G
G
M
P
P

说明/提示

【对题意的部分解释】

考虑 $\texttt{GMPP}$ 此串，那么依次进行以下过程：

• $\texttt{GMPP} \to \texttt{GMP}$。
• $\texttt{GMP} \to \texttt{GM}$。
• $\texttt{GM} \to \texttt{G}$。

因此，在这段话中，「公鸡」说的话总是对的。需要注意的时，比较相邻位置时，若对应的两人相同，则保留任意一个均可。

【样例 3】

见 $\bm{3.in}$ 与 $\bm{3.ans}$。

该样例满足测试点 $1 \sim 3$ 的约束条件。

【样例 4】

见 $\bm{4.in}$ 与 $\bm{4.ans}$。

该样例满足测试点 $4 \sim 9$ 的约束条件。

【样例 5】

见 $\bm{5.in}$ 与 $\bm{5.ans}$。

该样例满足测试点 $10 \sim 11$ 的约束条件。

【样例 6】

见 $\bm{6.in}$ 与 $\bm{6.ans}$。

该样例满足测试点 $12 \sim 15$ 的约束条件。

【样例 7】

见 $\bm{7.in}$ 与 $\bm{7.ans}$。

该样例满足测试点 $16$ 的约束条件。

【样例 8】

见 $\bm{8.in}$ 与 $\bm{8.ans}$。

该样例满足测试点 $17 \sim 18$ 的约束条件。

【样例 9】

见 $\bm{9.in}$ 与 $\bm{9.ans}$。

该样例满足测试点 $19$ 的约束条件。

【样例 10】

见 $\bm{10.in}$ 与 $\bm{10.ans}$。

该样例满足测试点 $20 \sim 22$ 的约束条件。

【样例 11】

见 $\bm{11.in}$ 与 $\bm{11.ans}$。

该样例满足测试点 $23 \sim 25$ 的约束条件。

【样例文件下载】

样例文件下载

【数据范围】

对于所有测试数据，均有：

• $1 \le t \le 5$。
• $1 \le n, m \le 10^6$。
• 对于所有 $1 \le i \le n$，均有 $str_i = \texttt{G/M/P}$。
• 在 $m$ 次操作中，对于所有 $1$ 操作，均有 $1 \le l \le r \le n$，对于所有 $2$ 操作，均有 $1 \le x \le n$，且 $k = \texttt{G/M/P}$。

测试点编号	$n$	$m$	$t$	特殊性质
$1 \sim 3$	$\le 50$		$\le 5$	无
$4 \sim 9$	$\le 5000$
$10 \sim 11$	$\le 200$	$\le 10^6$		A
$12 \sim 15$	$\le 10^6$			AB
$16$				C
$17 \sim 18$				AD
$19$				A
$20 \sim 22$	$\le 10^5$		$= 1$	无
$23 \sim 25$	$\le 10^6$		$= 5$

• 特殊性质 A：保证 $2$ 操作个数 $\le c + 1$ 个，$c$ 为测试点编号。
• 特殊性质 B：保证所有 $1$ 操作 $l = 1$。
• 特殊性质 C：保证任意时刻 $str$ 中不存在三个不同的人的谈话。
• 特殊性质 D：定义 $\mathbf f(str)$ 为所有时刻中 $str$ 中满足 $str_i \ne str_{i + 1}(1 \le i < n)$ 的 $i$ 的个数的最大值，满足有 $\mathbf f(str) \le 20$。