Dynamic Online 2D Points Query

To win the Turing Award, you must solve the following dynamic online 2D points problem.

There are n points in the plane, denoted by \((x_i, y_i)\), that all lie below the line \(y=x\) (i.e. \(y_i \le x_i\) for each point). You will perform q operations of two types:

1. Update Operation U i x y: Set \(x_i := x\) and \(y_i := y\).
2. Query Operation Q l r: Given a rectangle whose vertices are \((l,l)\), \((r,l)\), \((l,r)\) and \((r,r)\), find the minimum value of \(x-y\) among all points \((x,y)\) within the rectangle. A point is inside if and only if \(l\le x\le r\) and \(l\le y\le r\). If there is no point inside the rectangle, the answer is defined as \(0\).

Note that both types of operations are provided in an encrypted form; see the Input section for details.

inputFormat

The first line contains two integers \(n\) and \(q\), representing the number of points and the number of operations respectively.

The next \(n\) lines each contain two integers \(x\) and \(y\), indicating the initial coordinates of the points. It is guaranteed that \(y\le x\) for each point.

The following \(q\) lines describe the operations in encrypted form. Initially, set \(last=0\). For each operation, the provided integers are encrypted by performing a bitwise XOR with \(last\). (For the purpose of these sample test cases, the values are given in decrypted form.)

An update operation has the format:

U i x y

After decryption, it sets the i-th point to \((x,y)\).

A query operation has the format:

Q l r

After decryption, consider the rectangle with vertices \((l,l)\), \((r,l)\), \((l,r)\) and \((r,r)\), and output the minimum value of \(x-y\) among all points inside the rectangle. If no point lies within the rectangle, output \(0\). After processing a query, update \(last\) to be the answer of that query.

outputFormat

For each query operation, output a single line containing the answer.

sample

3 5
1 1
2 1
3 2
Q 1 3
U 2 3 2
Q 2 3
U 1 2 2
Q 2 3

0
1
0

</p>