F. Build XOR on a Segment
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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

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

Output

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

Example
Input
7
3 5 4 1 7 3 1
5
1 3 1
1 4 1
1 3 2
4 7 5
1 7 8
Output
2 1 3 3 0
Note

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