Background

The latest achievement in the data structure world. Forced online dynamic 2D point counting can already be done in linear time!

Problem Description

To win the Turing Award, you need to solve the following dynamic online 2D point counting problem.

There are $n$ points $(x_i, y_i)$ on the plane, arranged below the line $\bm{y=x}$ (that is, $\bm{y_i \le x_i}$ holds).

I will perform $q$ operations. There are two types of operations:

1. Update operation U i x y: set $x_i := x, y_i := y$. (That is, assign $x$ and $y$ to $x_i$ and $y_i$ respectively.)
2. Query operation Q l r: given a rectangle whose four vertices are $\bm{(l,l),(r,l),(l,r),(r,r)}$, find the minimum value of $x-y$ among all points $^\dagger$ $(x, y)$ inside the given rectangle. In particular, if the rectangle contains no points, the answer is defined as $\bm{0}$.

The two types of operations will be encrypted in some way. See the detailed requirements in the [Input Format] section below.

$^\dagger$: A point $(x, y)$ is inside the rectangle formed by $(l,l),(r,l),(l,r),(r,r)$ if and only if $l \le x \le r$ and $l \le y \le r$.

Input Format

The first line contains two integers $n$ and $q$.

The next $n$ lines each contain two integers $x_i$ and $y_i$, describing the coordinates of each point.

The following $q$ lines give the type of each operation and the encrypted values of its parameters. The true decrypted values of $i, x, y, l, r$ must all be XORed with your previous output answer (do not XOR before the first query operation). It is guaranteed that after decryption, the constraints $1 \le l \le r \le n$ and $1 \le i \le n$, $1 \le y \le x \le n$ hold.

Output Format

For each query operation, output one line containing your answer.

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

Hint

For all testdata, $1 \le n, q \le 5 \times 10^5$, and it is guaranteed that after decryption, $1 \le l \le r \le n$ and $1 \le i \le n$, $1 \le y \le x \le n$.

This problem uses bundled tests and enables subtask dependencies.

• Subtask 0 (5 points): $n, q \le 5 \times 10^3$.
• Subtask 1 (20 points): no update operations.
• Subtask 2 (25 points): satisfies special properties.
• Subtask 3 (20 points): $n, q \le 10^5$.
• Subtask 4 (30 points): no special restrictions.

Special properties (random data): the operation types, update positions, point coordinates (initial and after updates), and query ranges (the values of parameters $(i,x,y),(l,r)$) are generated independently and uniformly at random within the valid ranges.

Translated by ChatGPT 5