Flying Ship Story
Description
The memory limit of this problem (4 megabytes) is unusual!
There are many islands separated by the Byte Ocean. Clever people invented the flying ship such that they can travel to other lands. Today, millions of salesmen gather at Byteland to celebrate the annual international trading festival. You are maintaining the trading database here. Initially, the database is empty, then $q$ events will happen, each is one of the following two types:
- "1 x y w" ($1\leq x,y,w\leq 10^9$): A new good is on sale. It is from the $x$-th island, its type is numbered as $y$, and its price is $w$. Note that two goods can share the same type but from different islands.
- "2 x y" ($1\leq x,y\leq 10^9$): It is a query event. A salesman from the $x$-th island with the $y$-th type of good is searching for other types of goods from other islands. You need to report the price of the most expensive good, which is not from the $x$-th island, and the type of which is not $y$. When there is no finding, please report "0" instead. This is only for searching, the good that you find will not be deleted from the database.
Due to the low level of technology in Byteland, the space of the database is very limited, but you still need to maintain the database efficiently.
The first line of the input contains a single integer $q$ ($1 \leq q \leq 1\,000\,000$), denoting the number of events.
Each of the next $q$ lines describes an event in formats described in the statement above, except that some parameters are encrypted in order to enforce online processing.
Let $last$ be the previous price that you answered. Note that $last$ should be reset to $0$ at the beginning of the input. For each operation, $x$, $y$ and $w$ are encrypted: their actual values are $x \oplus last$, $y \oplus last$ and $w \oplus last$. In the expressions above, the symbol "$\oplus$" denotes the bitwise exclusive-or operation. Also, note that the constraints described in the statement above apply to the corresponding parameters only after decryption, the encrypted values are not subject to those constraints.
For each query, print a single line containing a single integer, denoting the price of the good that you find, or zero if there is no finding.
Input
The first line of the input contains a single integer $q$ ($1 \leq q \leq 1\,000\,000$), denoting the number of events.
Each of the next $q$ lines describes an event in formats described in the statement above, except that some parameters are encrypted in order to enforce online processing.
Let $last$ be the previous price that you answered. Note that $last$ should be reset to $0$ at the beginning of the input. For each operation, $x$, $y$ and $w$ are encrypted: their actual values are $x \oplus last$, $y \oplus last$ and $w \oplus last$. In the expressions above, the symbol "$\oplus$" denotes the bitwise exclusive-or operation. Also, note that the constraints described in the statement above apply to the corresponding parameters only after decryption, the encrypted values are not subject to those constraints.
Output
For each query, print a single line containing a single integer, denoting the price of the good that you find, or zero if there is no finding.
5
1 2 3 1
1 4 5 2
2 2 2
2 3 7
2 3 4
2
1
0