题目背景

题目来源：$2014$ 年湖北省队互测Week1

资源来源：链接

题目描述

万物初始之前，宇宙是无边无际混沌的黑暗，只有上帝之灵穿行其间。

上帝对这无边的黑暗十分不满，就一挥手说:“要有光”，于是世间就有了光。从此，世间 就有了昼与夜的交替。这是上帝创世的第一天。

第二天，上帝仍不满意眼前空洞的景象，就一挥手说：“要有零”。于是世间出现了第一个数：$0$。

第三天，上帝对只有 $0$ 很不满意，就一挥手说：“要有非零数”。于是上帝开始创造新数，每个新数用一个已经创造出来的数的有序对表示，即：

$$x = (x_L, x_R)$$

于是世间出现了 $(0, 0), (0, (0, 0)), ((0, 0), 0), ((0, 0), (0, 0)), ...$。到了晚上，各种各样千奇百怪的数在大地上奔腾。 （注：上帝造的这个 “数” 与普通的自然数、有理数之类的不同，这种数是以如上所述的方式递归定义的，总是数对里面是数对，拆分到最后会得到不可再拆的 $0$）

第四天，上帝看到各个数不分彼此，就一挥手说：“要有区别”。于是为了区分每个数，上帝定义等于：

1. $0 = 0$ 。

2. 对于任意 $x_L, x_R, y_L, y_R$，若 $x_L = y_L$ 且 $x_R = y_R$，则 $(x_L, x_R) = (y_L, y_R)$。

3. 对于任意 $x, y$，$x = y$ 当且仅当满足以上条件之一。反之记作 $x \not = y$。

第五天，上帝看到各个数乱成一团，就一挥手说：“要有序”。于是为了比较每个数，上帝定义小于：

1. 对于任意 $x$，若 $x\not = 0$，则 $0 < x$。
2. 对于任意 $x_L, x_R, y_L, y_R$，若 $x_L < y_L$，则 $(x_L, x_R) < (y_L, y_R)$ 。
3. 对于任意 $x_L, x_R, y_L, y_R$，若 $x_L = y_L$ 且 $x_R < y_R$，则 $(x_L, x_R) < (y_L, y_R)$。
4. 对于任意 $x, y$，$x < y$ 当且仅当满足以上条件之一。反之记作 $x\not < y$。

在此基础上定义小于等于：$x ≤ y \iff x < y$ 或 $x = y$ 。容易发现：

1. $x ≤ y, y ≤ x ⇒ x = y$ 。
2. $x ≤ y, y ≤ z ⇒ x ≤ z$ 。
3. $x ≤ y$ 或 $y ≤ x$ 。

进而定义：

1. $x > y \Longleftrightarrow y < x$ 。
2. $x ≥ y \Longleftrightarrow x\not < y$。

至此万物欣欣向荣，和睦一堂。

第六天，由于之前沉迷与算术而忘记去造核酸和蛋白质，所以上帝没办法造人。但是上帝不甘心，就一挥手说：“要有跳蚤”，于是用泥巴捏出了神奇生物跳蚤。

上帝用五天的时间造出天地万物，又在第六天造出了唯一的生命——跳蚤。上帝看到天地万物井然有序、生生不息，自己造的跳蚤正在开心地和数学玩耍，很高兴，便决定把第七天作为休息的日子。

跳蚤每天的生活很简单。一天开始时，他会取一个长度为 $n$ 的数组 $a[1,2,\cdots,n]$，初始时均为 $0$。

接着他会不断地做下列两件事之一：

1. 在头脑中产生三个正整数 $l, r, k$，然后把 $a[k]$ 重新赋值为 $(a[l], a[r])$ 。特别地，如果 $l = k$ 或 $r = k$ 也是合法的，这不会导致错误，因为跳蚤总是先默默算出 $(a[l], a[r])$ 再给 $a[k]$ 赋值。

   保证 $1 ≤ l, r, k ≤ n$。

2. 在头脑中产生两个正整数 $l, r$，然后计算 $a[l], a[l + 1], \cdots, a[r − 1], a[r]$ 中的最大值。

   保证 $1 ≤ l ≤ r ≤ n$。

跳蚤当然知道怎么做啦！但是他想考考你……

输入格式

第一行两个正整数 $n, m$，表示长度为 $n$ 的数组，共 $m$ 个操作。接下来 $m$ 行每行表示一个操作:

1. C l r k : 赋值操作，执行 $a[k] = (a[l], a[r])$ 。

2. Q l r: 询问操作，计算 $a[l], a[l + 1], ..., a[r − 1], a[r]$ 中的最大值。输出最大值对应的下标。 如果有多个最大值那么取下标最小的那一个。

输出格式

对于每个询问操作输出一行表示相应的结果。

5 10 
C 1 1 1 
C 2 1 2 
Q 1 2 
C 4 4 4 
C 5 5 5 
Q 4 5 
Q 3 3 
C 4 2 3 
C 4 4 4 
Q 3 4

2
4
3
3

提示

$$\def\arraystretch{1.5} \begin{array}{c|l|l} \hline\hline \rm Task~Id & n & m \\ \hline\hline 1 & =10 & =50 \\ \hline 2 & =5\times 10^4 & \leq 2\times 10^5 \\ \hline 3 & =5\times 10^4 & \leq 2\times 10^5 \\ \hline 4 & =6\times 10^4 & \leq 5\times 10^5 \\ \hline 5 & =6\times 10^4 & \leq 5\times 10^5 \\ \hline 6 & =8\times 10^4 & \leq 2\times 10^5 \\ \hline 7 & =8\times 10^4 & \leq 2\times 10^5 \\ \hline 8 & =10^5 & \leq 5\times 10^5 \\ \hline 9 & =10^5 & \leq 5\times 10^5 \\ \hline 10 & =10^5 & \leq 5\times 10^5 \\ \hline\hline \end{array} $$