长度为 $N$ 的序列 $A_1, A_2, \ldots, A_N$ 给定。请编写程序执行以下查询。

• i j k：输出由 $A_i, A_{i+1}, \ldots, A_j$ 构成的子序列中大于 $k$ 的元素的个数。

输入格式

第一行给出序列的长度 $N$ $(1 \le N \le 100{,}000)$。

第二行给出 $A_1, A_2, \ldots, A_N$。$(1 \le A_i \le 10^9)$

第三行给出查询的个数 $M$ $(1 \le M \le 100{,}000)$。

接下来 $M$ 行每行给出 $a, b, c$。需要利用 $a, b, c$ 构造查询。

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

last_ans 是上一次查询的答案，初始值为 $0$。异或后的结果满足 $1 \le i \le j \le n$，$1 \le k \le 10^9$。

输出格式

对于每个查询，在一行中输出答案。

样例

输入 1

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

输出 1

2
0
3