题目背景

数据结构界的最新成果！强制在线动态二维数点已经可以做到线性时间！

题目描述

要拿到图灵奖，你需要解决下面这道动态在线二维数点问题：

平面上有 $n$ 个点 $(x_i,y_i)$，排列在 $\bm{y=x}$ 的直线下方（即，$\bm{y_i\le x_i}$ 成立）。

我会进行 $q$ 次操作，操作有两种类型：

1. 修改操作 U i x y：令 $x_i:=x,y_i:=y$。（即，将 $x_i$ 和 $y_i$ 分别赋值为 $x$ 和 $y$。）
2. 询问操作 Q l r：给出一个四个顶点分别是 $(l,l),(r,l),(l,r),(r,r)$ 的矩形，求出在给出的矩形内的点 $^\dagger$ $(x,y)$ 中最小的 $x-y$ 的值。特别地，规定当矩形没有包含任何一个点时答案为 $\bm{0}$。

两种操作会以某种方式进行加密，详细要求见下方【输入格式】一栏。

$^\dagger$：点 $(x,y)$ 在 $(l,l),(r,l),(l,r),(r,r)$ 所构成的矩形内，当且仅当 $l\le x\le r$ 且 $l\le y\le r$。

输入格式

第一行两个整数 $n$ 和 $q$。

随后 $n$ 行，每行两个整数 $x_i$ 和 $y_i$ 描述每个点的坐标。

接下来 $q$ 行，给出每个操作的类型和对应参数的加密值。解密后的真实的参数 $i,x,y,l,r$ 的值，均要异或你上一次输出的答案（第一次询问操作前不异或）。我会保证解密后 $1\le l\le r\le n$ 和 $1\le i\le n$，$1\le y\le x\le n$ 的约束存在。

输出格式

对每个询问操作，输出一行你的答案。

5 6
4 1
4 1
4 2
4 1
5 2
Q 2 5
U 6 6 3
Q 3 7
Q 1 6
U 2 4 2
Q 2 3

2
2
0
0

提示

对于所有测试数据，$1\le n,q\le 5\times 10^5$，并且保证解密后的 $1\le l\le r\le n$ 且 $1\le i\le n$，$1\le y\le x\le n$。

本题采用捆绑测试，并开启子任务依赖。

• Subtask 0（5 points）：$n,q\le 5\times 10^3$。
• Subtask 1（20 points）：无修改操作。
• Subtask 2（25 points）：满足特殊性质。
• Subtask 3（20 points）：$n,q\le 10^5$。
• Subtask 4（30 points）：无特殊限制。

特殊性质（数据随机）：操作类型、修改的位置、初始时和修改后的点的坐标和询问区间（参数 $(i,x,y),(l,r)$ 的值）在合法范围内独立地均匀随机生成。