K-Query Online

Source: SPOJ

Version: Phuoc Hung OJ Extended

Problem

Queries are online. Let last be the previous answer, initially $0$. Decode $i=x\oplus last$, $j=y\oplus last$, $k=z\oplus last$. Clamp $i$ to at least $1$ and $j$ to at most $n$. If $i>j$, the answer is $0$; otherwise count values greater than $k$ in $a_i..a_j$. Set last to that answer.

Input

The first line contains $n$, the second line contains the array, the third line contains $q$, and each following line contains encoded values $x,y,z$.

Output

Print each decoded query answer in order.

Subtasks

Subtask 1 (20%)

• $n\le 30$, number of queries $\le 30$.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, number of queries $\le 3000$.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n\le30000$
• $1\le q\le200000$
• $1\le a_i\le10^9$

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

Explanation

Every query depends on the previous result, so queries cannot be reordered. The sample answers are 1,1,0,0,2.