Problem 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\leq 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 \bigoplus a \leq b\ \ $ where $\bigoplus$ is the binary Bitwise XOR operation.

Input

There is only one test case for this question.

In the first line contains a positive integer $n$ ($n \leq 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 \leq c_i \leq n$)of the i-th position.

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

In the next Q line, each line has four positive integers $l$, $r$, $a$, $b$ ($1 \leq l \leq r \leq n, a \leq n+1,b \leq 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.

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