21092번 - Rectangle Painting 다국어

문제

There is an cell grid infinite in left, right, and upwards directions (all the cells with coordinates $(x, y)$ with $x \in \mathbb{Z},ドル $y \ge 0$ exist). Initially all the cells are white. You have to process $q$ queries of two types:

1. $y_{i}$ $l_{i}$ $r_{i}$: paint all cells $(x, y_{i})$ for $l_{i} \le x \le r_{i}$ black. If the cell is already black, its color doesn't change.
2. $l_{i}$ $r_{i}$: consider all cells with $x$ coordinate on the segment $[l_{i}; r_{i}]$. Find the highest cell such that all cells exactly under it are black. Formally, you have to find maximal $h$ such that $\exists \: x \in [l_{i}; r_{i}] \: \forall \: y \in [0;h)$ cell $(x, y)$ is black.

To enforce processing the queries online they are encrypted using previous answers.

입력

The first line contains one integer $q$ (1ドル \le q \le 10^{5}$) --- the number of queries to process.

The next $q$ lines will contain encrypted descriptions of queries. Let $S$ be the sum of answers to all queries of second type processed so far.

Each description has form either 1ドル$ $(y_{i} \oplus S)$ $(l_{i} \oplus S)$ $(r_{i} \oplus S)$ or 2ドル$ $(l_{i} \oplus S)$ $(r_{i} \oplus S)$. It is guaranteed that 0ドル \le y_{i} \le 2 \cdot 10^{5},ドル 0ドル \le l_{i} \le r_{i} \le 2 \cdot 10^{5}$. Note that the guarantees are given on parameters after decryption, the numbers in input might not fit in 32-bit integers.

Don't forget to add the new answer to $S$ after each query of the second type.

출력

Print the answers to all queries of the second type on separate lines.

제한

힌트