Given a sequence of n numbers a₁, a₂, ..., a_n and a number of k-queries. A k-query is a triple (i, j, k) (1 ≤ i ≤ j ≤ n). For each k-query (i, j, k), you have to return the number of elements greater than k in the subsequence a_i, a_i+1, ..., a_j.

Input

• Line 1: n (1 ≤ n ≤ 30000).
• Line 2: n numbers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).
• Line 3: q (1 ≤ q ≤ 200000), the number of k- queries.
• In the next q lines, each line contains 3 numbers a, b, c representing a k-query. You should do the following:
  • i = a xor last_ans
  • j = b xor last_ans
  • k = c xor last_ans
  After that 1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 10⁹ holds.
  Where last_ans = the answer to the last query (for the first query it's 0).

Output

For each k-query (i, j, k), print the number of elements greater than k in the subsequence a_i, a_i+1, ..., a_j in a single line.

Example

Input:
6
8 9 3 5 1 9
5
2 3 5
3 3 7
0 0 11
0 0 2
3 7 4

Output:
1
1
0
0
2

[Edited by EB]

• if i < 1: i = 1
• if j > n: j = n
• if i > j: ans = 0