There is an array $$$a$$$ of $$$2^{30}$$$ integers, indexed from $$$0$$$ to $$$2^{30}-1$$$. Initially, you know that $$$0 \leq a_i < 2^{30}$$$ ($$$0 \leq i < 2^{30}$$$), but you do not know any of the values. Your task is to process queries of two types:
Note that the queries are encoded. That is, you need to write an online solution.
The first line contains a single integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of queries.
Each of the next $$$q$$$ lines describes a query. It contains one integer $$$t$$$ ($$$1 \leq t \leq 2$$$) — the type of query.
The given queries will be encoded in the following way: let $$$last$$$ be the answer to the last query of the second type that you have answered (initially, $$$last = 0$$$). If the last answer was $$$-1$$$, set $$$last = 1$$$.
and, if $$$l > r$$$, swap $$$l$$$ and $$$r$$$.
This means you got an update that the bitwise xor of the subarray $$$[l, r]$$$ is equal to $$$x$$$ (notice that you need to ignore updates that contradict previous updates).
and, if $$$l > r$$$, swap $$$l$$$ and $$$r$$$.
For the given query, you need to print the bitwise xor of the subarray $$$[l, r]$$$. If it is impossible to know, print $$$-1$$$. Don't forget to change the value of $$$last$$$.
It is guaranteed there will be at least one query of the second type.
After every query of the second type, output the bitwise xor of the given subarray or $$$-1$$$ if it is still impossible to know.
12
2 1 2
2 1 1073741822
1 0 3 4
2 0 0
2 3 3
2 0 3
1 6 7 3
2 4 4
1 0 2 1
2 0 0
2 4 4
2 0 0
-1
-1
-1
-1
5
-1
6
3
5
4
1 5 5 9
1 6 6 5
1 6 5 10
2 6 5
12
In the first example, the real queries (without being encoded) are:
In the second example, notice that after the first two updates we already know that $$$a_5 \oplus a_6 = 12$$$, so the third update is contradicting, and we ignore it.
Name |
---|