CF2170F.Build XOR on a Segment

You are given an array of $n$ integers $a_1, a_2, \dots, a_n$, where all numbers are from $1$ to $2^{12} - 1$.

You have to process $q$ queries. Each query is defined by three integers $l_i, r_i, x_i$: you need to find the smallest set $S = {s_1, s_2, \dots, s_k}$ that satisfies the following conditions:

• each $s_j$ is equal to some element from the subarray from the $l_i$-th position to the $r_i$-th position inclusive;
• $s_1 \oplus s_2 \oplus \dots \oplus s_k = x_i$, where $\oplus$ denotes bitwise XOR.

给你一个包含 $n$ 个整数的数组 $a_1, a_2, \dots, a_n$，其中所有数均在 $1$ 到 $2^{12} - 1$ 之间。

你需要处理 $q$ 个查询。每个查询由三个整数 $l_i, r_i, x_i$ 定义：你需要找出满足以下条件的最小集合 $S = \{s_1, s_2, \dots, s_k\}$：

• 每个 $s_j$ 等于子数组（从第 $l_i$ 个位置到第 $r_i$ 个位置，含端点）中的某个元素；
• $s_1 \oplus s_2 \oplus \dots \oplus s_k = x_i$，其中 $\oplus$ 表示按位异或运算。

The first line contains one integer $n$ ($2 \le n \le 10^4$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2^{12} - 1$).

The third line contains one integer $q$ ($1 \le q \le 10^6$).

Then $q$ lines follow. The $i$-th of them contains three integers $l_i, r_i, x_i$ ($1 \le l_i \le r_i \le n$; $1 \le x_i \le 2^{12} - 1$).

第一行包含一个整数 $n$（$2 \le n \le 10^4$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2^{12} - 1$）。

第三行包含一个整数 $q$（$1 \le q \le 10^6$）。

接下来是 $q$ 行。其中第 $i$ 行包含三个整数 $l_i, r_i, x_i$（$1 \le l_i \le r_i \le n$；$1 \le x_i \le 2^{12} - 1$）。

For each query, print one integer — the minimum size of the required set. If such a set does not exist, print $0$.

对于每个查询，输出一个整数——所需集合的最小大小。如果这样的集合不存在，则输出 $0$。

Consider the queries from the example:

• in the first query, you can choose $S = {5, 4}$;
• in the second query, you can choose $S = {1}$;
• in the third query, you can choose $S = {4, 3, 5}$;
• in the fourth query, you can choose $S = {1, 3, 7}$.

考虑示例中的查询：

• 在第一个查询中，你可以选择 $S = {5, 4}$；
• 在第二个查询中，你可以选择 $S = {1}$；
• 在第三个查询中，你可以选择 $S = {4, 3, 5}$；
• 在第四个查询中，你可以选择 $S = {1, 3, 7}$。