题意

给定一个长度为 $n$ 的数组 $C$，以及 $m$ 条指令，每条指令四个数字 $l,r,a,b$，表示询问区间 $[l,r]$ 中有多少种数值不同的$C_i$，使得$C_i\ xor \ a \le b$。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数，表示数组 $C$。

第三行输入一个整数 $m$ 表示指令数。

接下来 $m$ 行，每行一条指令

输出格式

对于每次询问，输出一行一个整数表示答案。

样例

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

数据范围

本题共 $4$ 个测试点。

对所有的测试点，保证 $1\le n,m\le 10^5,1\le C_i\le n,1\le l \le r\le n,a\le n+1,b\le n+1$。

第一个测试点满足 $n,m\le5000$。

第二个测试点满足给出的数组是 $n$ 的一个排列且 $l=1$。

第三个测试点满足给出的数组是 $n$ 的一个排列。