Description

Mr W likes interval counting.

One day,Mr W constructed a sequence of length n, each position of this sequence has a weight c $(c \leqslant n)$.

There are a total of Q queries, and each query is given an interval (l,r) and two parameters a, b, and ask how many kinds of weights of this interval satisfy $c \leqslant a \leqslant b$ where $⨁$ is the binary Bitwise $XOR$ operation.

Format

Input

There is only one test case for this question.

In the first line contains a positive integer n $(n \leqslant 100000)$ represents the length of the sequence.

In the second line contains n positive integers, The i-th number in the sequence represents the weight $c_i$ $(1 \leqslant c_i \leqslant n)$of the i-th position.

In the third line, a positive integer Q $(Q \leqslant 100000)$ represents the number of queries.

In the next Q line, each line has four positive integers l, r, a, b $(1 \leqslant l \leqslant r \leqslant n,a \leqslant n+1,b \leqslant n+1)$, which represent the parameters of the query.

Output

For each query, output an integer on a line to represent the number of weights that meet the conditions.

Samples

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

2
1
2
1