CF1044D.Deduction Queries

There is an array $a$ of $2^{30}$ integers, indexed from $0$ to $2^{30}-1$. Initially, you know that $0 \leq a_i \lt 2^{30}$ ($0 \leq i \lt 2^{30}$), but you do not know any of the values. Your task is to process queries of two types:

• 1 l r x: You are informed that the bitwise xor of the subarray $[l, r]$ (ends inclusive) is equal to $x$. That is, $a_l \oplus a_{l+1} \oplus \ldots \oplus a_{r-1} \oplus a_r = x$, where $\oplus$ is the bitwise xor operator. In some cases, the received update contradicts past updates. In this case, you should ignore the contradicting update (the current update).
• 2 l r: You are asked to output the bitwise xor of the subarray $[l, r]$ (ends inclusive). If it is still impossible to know this value, considering all past updates, then output $-1$.

Note that the queries are encoded. That is, you need to write an online solution.

存在一个长度为 $2^{30}$ 的整数数组 $a$，下标范围从 $0$ 到 $2^{30}-1$。初始时，你知道对所有 $i$（$0 \leq i < 2^{30}$）均有 $0 \leq a_i < 2^{30}$，但你并不知道任何具体的 $a_i$ 值。你的任务是处理两类查询：

• 1 l r x：你被告知子数组 $[l, r]$（含端点）的按位异或值等于 $x$。即 $a_l \oplus a_{l+1} \oplus \ldots \oplus a_{r-1} \oplus a_r = x$，其中 $\oplus$ 表示按位异或运算。在某些情况下，新收到的更新与之前已接收的更新矛盾。此时，你应忽略该矛盾的更新（即忽略当前这条更新）。
• 2 l r：你需要输出子数组 $[l, r]$（含端点）的按位异或值。如果根据所有已接收的更新仍无法确定该值，则输出 $-1$。

注意：这些查询是经过编码的，即你需要编写一个在线解法。

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$.

• If $t = 1$, three integers follow, $l'$, $r'$, and $x'$ ($0 \leq l', r', x' \lt 2^{30}$), meaning that you got an update. First, do the following:

  $l = l' \oplus last$, $r = r' \oplus last$, $x = x' \oplus last$

  and, if $l \gt 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).

• If $t = 2$, two integers follow, $l'$ and $r'$ ($0 \leq l', r' \lt 2^{30}$), meaning that you got a query. First, do the following:

  $l = l' \oplus last$, $r = r' \oplus last$

  and, if $l \gt 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.

第一行包含一个整数 $q$（$1 \leq q \leq 2 \cdot 10^5$），表示查询的次数。

接下来的 $q$ 行，每行描述一个查询。每行包含一个整数 $t$（$1 \leq t \leq 2$），表示查询类型。

这些查询将按如下方式编码：令 $last$ 表示你上一次回答的第二类查询的答案（初始时 $last = 0$）；若上一次答案为 $-1$，则令 $last = 1$。

• 若 $t = 1$，其后跟着三个整数 $l'$、$r'$ 和 $x'$（$0 \leq l', r', x' < 2^{30}$），表示一次更新操作。首先执行以下步骤：

  $l = l' \oplus last$, $r = r' \oplus last$, $x = x' \oplus last$

  若 $l > r$，则交换 $l$ 和 $r$。

  这意味着你收到一条更新信息：子数组 $[l, r]$ 的按位异或值等于 $x$（注意：需忽略与先前更新矛盾的更新）。

• 若 $t = 2$，其后跟着两个整数 $l'$ 和 $r'$（$0 \leq l', r' < 2^{30}$），表示一次查询操作。首先执行以下步骤：

  $l = l' \oplus last$, $r = r' \oplus last$

  若 $l > r$，则交换 $l$ 和 $r$。

  对于该查询，你需要输出子数组 $[l, r]$ 的按位异或值；若无法确定，输出 $-1$。别忘了更新 $last$ 的值。

保证至少存在一个第二类查询。

After every query of the second type, output the bitwise xor of the given subarray or $-1$ if it is still impossible to know.

每次执行第二种类型的查询后，输出给定子数组的按位异或值；如果此时仍无法确定该值，则输出 $-1$。

In the first example, the real queries (without being encoded) are:

• 12

• 2 1 2

• 2 0 1073741823

• 1 1 2 5

• 2 1 1

• 2 2 2

• 2 1 2

• 1 2 3 6

• 2 1 1

• 1 1 3 0

• 2 1 1

• 2 2 2

• 2 3 3

• The answers for the first two queries are $-1$ because we don't have any such information on the array initially.

• The first update tells us $a_1 \oplus a_2 = 5$. Note that we still can't be certain about the values $a_1$ or $a_2$ independently (for example, it could be that $a_1 = 1, a_2 = 4$, and also $a_1 = 3, a_2 = 6$).

• After we receive all three updates, we have enough information to deduce $a_1, a_2, a_3$ independently.

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.

在第一个例子中，真实的查询（未编码）如下：

• 12

• 2 1 2

• 2 0 1073741823

• 1 1 2 5

• 2 1 1

• 2 2 2

• 2 1 2

• 1 2 3 6

• 2 1 1

• 1 1 3 0

• 2 1 1

• 2 2 2

• 2 3 3

• 前两个查询的答案为 $-1$，因为我们初始时对数组没有任何相关信息。

• 第一个更新告诉我们 $a_1 \oplus a_2 = 5$。注意，我们仍无法独立确定 $a_1$ 或 $a_2$ 的具体值（例如，可能有 $a_1 = 1, a_2 = 4$，也可能有 $a_1 = 3, a_2 = 6$）。

• 在接收全部三个更新后，我们便拥有了足够信息，可独立推导出 $a_1, a_2, a_3$ 的值。

在第二个例子中，请注意：前两个更新之后，我们已知 $a_5 \oplus a_6 = 12$，因此第三个更新与此矛盾，将被忽略。