Given a sequence $A_1, A_2, \ldots, A_N$ of length $N$, write a program that processes the following query:

• i j k: Output the number of elements greater than $k$ in the subsequence consisting of $A_i, A_{i+1}, \ldots, A_j$.

Input

The first line contains the length of the sequence $N$ $(1 \le N \le 100{,}000)$.

The second line contains $A_1, A_2, \ldots, A_N$. $(1 \le A_i \le 10^9)$

The third line contains the number of queries $M$ $(1 \le M \le 100{,}000)$.

The next $M$ lines each contain $a, b, c$. The query is constructed using $a, b, c$ as follows:

• i = a xor last_ans
• j = b xor last_ans
• k = c xor last_ans

last_ans is the answer to the previous query, initially $0$. The results of the xor operations satisfy $1 \le i \le j \le n$, $1 \le k \le 10^9$.

Output

For each query, output the answer on a separate line.

Examples

Input 1

5
5 1 2 3 4
3
2 4 1
6 6 6
1 5 2

Output 1

2
0
3