题目描述

给你一个长为 $n$ 的序列，然后对序列进行 $m$ 次操作，操作有两种：

• M l r v：把区间 $[l,r]$ 的所有数都改成 $v$。
• Q l r k v：询问区间 $[l,r]$ 中从左到右第 $k$ 个 $v$ 的下标（下标从 $1$ 开始），不存在则输出 $0$。
  为了防止你采用离线算法，本题强制在线，每次输入的所有整数都需要异或上次询问的答案（如果还没有进行过询问则为 $0$），得到的才是真正的输入。

输入格式

第一行两个非负整数，分别表示 $n,m$。
第二行 $n$ 个正整数，表示原来的序列。
以下 $m$ 行，每行描述一个操作，格式如上所述。

输出格式

对于每个 $ Q $ 操作，单独一行输出一个整数表示答案。

样例

input

5 5
2 3 3 3 3
Q 2 4 3 3
M 7 0 2
Q 0 1 5 2
M 5 5 7
Q 7 1 6 7

output

4
4
0

原本的输入应该是

5 5
2 3 3 3 3
Q 2 4 3 3
M 3 4 6
Q 4 5 1 6
M 1 1 3
Q 3 5 2 3

数据范围与提示

$n,m\le 10^5$，保证任何时刻均有 $0\le a_i\le 10^9$。