D. Range Xor Subsequence Query
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence of $$$n$$$ integers $$$a_1, \dots , a_n$$$. Your task is to process the $$$q$$$ queries of the following:

- Given $$$l, r, x$$$, check if it's possible to choose several integers from $$$a_l, a_{l+1}, \dots , a_r$$$ such that their bitwise XOR is $$$x$$$. Print "Yes" if possible, print "No" otherwise.

Input

The first line of input contains a single integer $$$n \ (1 \le n \le 10^5)$$$.

The second line contains $$$n$$$ integers $$$a_1, \dots, a_n \ (0 \le a_i \lt 2^{60})$$$ denoting the sequence.

Then the next line contains a single integer $$$q \ (1 \le q \le 5 \times 10^5)$$$.

Then, for the following $$$q$$$ lines, each line contains $$$3$$$ integers $$$l, r, x \ (1 \le l \le r \le n, 0 \le x \lt 2^{60})$$$ denoting a query.

Output

For each query, print a single line of 'Yes' or 'No'.

Example
Input
5
2 4 1 16 8
4
1 3 20
2 4 20
1 5 31
1 5 32
Output
No
Yes
Yes
No