5304: I love counting
内存限制：256 MB
时间限制：10.000 S
评测方式：文本比较
命题人：
提交：6
解决：3
题目描述
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≤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⨁a≤b where ⨁ is the binary Bitwise XOR operation.
One day,Mr W constructed a sequence of length n, each position of this sequence has a weight c (c≤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⨁a≤b where ⨁ is the binary Bitwise XOR operation.
输入
There is only one test case for this question.
In the first line contains a positive integer n (n≤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 ci (1≤ci≤n)of the i-th position.
In the third line, a positive integer Q (Q≤100000) represents the number of queries.
In the next Q line, each line has four positive integers l, r, a, b (1≤l≤r≤n,a≤n+1,b≤n+1), which represent the parameters of the query.
In the first line contains a positive integer n (n≤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 ci (1≤ci≤n)of the i-th position.
In the third line, a positive integer Q (Q≤100000) represents the number of queries.
In the next Q line, each line has four positive integers l, r, a, b (1≤l≤r≤n,a≤n+1,b≤n+1), 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