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.

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