Description

The basement where Flandre is can be abstracted as a huge 2D Cartesian coordinate system. Flandre will perform $q$ actions. Each action is as follows:

• 1 x y v means Flandre summons a new phantom at coordinate $(x,y)$, and this phantom has $v$ units of power.

• 2 means query, among the existing phantoms, what the maximum value of "Flandre Distance" is.

• 3 a means query: if the $a$-th summoned phantom is ignored, then among the remaining phantoms, what the maximum value of "Flandre Distance" is.

Note:

Let the $i$-th summoned phantom have index $i$, coordinate $(x_i,y_i)$, and power $v_i$.

The "Flandre Distance" between two phantoms with indices $u,v$ is $|x_u-x_v|+|y_u-y_v|+v_{\max(u,v)}$.

In particular, the "Flandre Distance" from phantom $i$ to itself is $v_i$.

In operation $3$, the $a$-th summoned phantom only does not participate in this query, rather than being removed.

Input Format

The first line contains an integer $q$, the number of operations.

Then follow $q$ lines, each containing several integers. The input format is the same as in the problem description.

Note: Since Flandre's emotions are unstable, in operation $1$, the actual input is:

$$x'=x \operatorname{ xor } (\text{lastans} \bmod 3)$$$$y'=y \operatorname{ xor } (\text{lastans} \bmod 3)$$$$v'=v \operatorname{ xor } (\text{lastans} \bmod 3)$$

The meanings of the operations are:

• $\operatorname{xor}$ denotes the bitwise XOR operation.

• $\text{lastans}$ denotes the answer of the previous operation $2$ or $3$. Initially, $\text{lastans}=0$.

Output Format

Output several lines in total, each containing one integer, which is the answer for each operation $2$ or $3$.

6
1 4 -4 0
1 -3 -1 0
1 -1 -1 0
2
3 2
3 3

10
8
10

Hint

Constraints and Notes

"This problem uses bundled testdata: a subtask is accepted if and only if all test points in that subtask are accepted".

Subtask ID	$q \le$	Special Property	Score
$1$	$500$	None	$5$
$2$	$5 \times 10^3$	A	$10$
$3$	$10^5$		$20$
$4$		None	$25$
$5$	$2 \times 10^6$		$40$

Property A means there is no operation $3$.

For $100\%$ of the data, $-10^8 \le x,y,v \le 10^8$. Let the number of phantoms at some moment be $c$, then $1 \le a \le c$.

The testdata guarantees that any two phantoms have different coordinates, and that at least $3$ points have been inserted when querying $2$ or $3$.

Translated by ChatGPT 5