P7470 [NOI Online 2021 提高组] 岛屿探险

凇睦是一个喜欢探险的女孩子，这天她到一片海域上来探险了。 在这片海域上一共有 $n$ 座岛屿排成一排，标号为 $1,2,3, \ldots ,n$。每座岛屿有两个权值，分别为劳累度 $a_i$ 和有趣度 $b_i$。 对于一座劳累度为 $a$，有趣度为 $b$ 的小岛，如果这个小岛满足 $(a\oplus c) \leq \min(b,d)$，凇睦到这座岛探险就会感到开心，其中 $c$ 表示凇睦到岛上去之前就有的劳累度（称作初始劳累度），同理 $d$ 代表凇睦的初始有趣度。$\oplus$ 表示二进制异或（即二进制表示下不进位的加法）。 为了玩的更尽兴，凇睦会向你询问 $q$ 次，每次给出一个区间 $[l_i,r_i]$ 和两个数 $c_i,d_i$，你需要告诉凇睦若她的初始劳累度为 $c_i$，初始有趣度为 $d_i$，则有多少个标号在 $[l_i,r_i]$ 这个区间内的岛屿能使凇睦探险时感到开心。

无

无

测试点 $1,2$ 满足 $1\leq n,q\leq 5000$。 测试点 $3,4$ 满足 $1\leq n,q\leq 10^4$。 测试点 $5,6,7$ 满足 $1\leq n,q\leq 10^5$ 且 $\max\{d_i\}\leq \min\{b_i\}$。 测试点 $8,9,10,11$ 满足 $1\leq n,q\leq 10^5$ 且 $\min\{d_i\}\geq \max\{b_i\}$。 测试点 $12,13$ 满足 $1\leq n,q\leq 10^5$ 且 $l_i=1,r_i=n$。 测试点 $14,15,16$ 满足 $1\leq n,q\leq 7\times 10^4$。 测试点 $17,18,19,20$ 满足 $1\leq n,q\leq 10^5$。 所有数据满足 $1\leq n,q\leq 10^5$， $1\leq a_i,b_i,c_i,d_i\leq 2^{24}-1$。