题目描述

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 binaryBitwise XOR operation.

输入格式

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,b \\leq n)$,which represent the parameters of the query.

输出格式

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

提示

Added by FZSF.