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. 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)). For each query, print one integer — the minimum size of the required set. If such a set does not exist, print (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\}).