[REMOI 114514 Loli组]给雷姆酱送白丝

题目描述

Shiro是雷姆的舔狗。有一次Shiro在与雷姆的视频通话中得知雷姆的白丝已经很久没有换过了，如果Shiro愿意给雷姆送上一双崭新的白丝，那么雷姆就会将她用了很久的白丝送给Shiro。这对于舔狗Shiro来说可是不可多得的好机会，他内心十分坚毅！

Shiro是一名大陆国人，而雷姆是日本鬼族。Shiro已经到达了韩国，他打算依靠连接两岸的海域上的岛屿来到达日本。

在这片海域上一共有 $n$ 座岛屿排成一排，标号为 $1,2,3, \ldots ,n$。每座岛屿有两个权值，分别为劳累度 $a_i$ 和坚毅度 $b_i$。

对于一座劳累度为 $a$，坚毅度为 $b$ 的小岛，如果这个小岛满足 $(a\oplus c) \leq \min(b,d)$，Shiro到达这座岛探险就会对拿到雷姆的白丝充满信心，其中 $c$ 表示Shiro到岛上去之前就有的劳累度（称作初始劳累度），同理 $d$ 代表Shiro的初始坚毅度。$\oplus$ 表示二进制异或（即二进制表示下不进位的加法）。

为了更加方便地拿到雷姆的白丝，Shiro会向你询问 $q$ 次，每次给出一个区间 $[l_i,r_i]$ 和两个数 $c_i,d_i$，你需要告诉Shiro若她的初始劳累度为 $c_i$，初始坚毅度为 $d_i$，则有多少个标号在 $[l_i,r_i]$ 这个区间内的岛屿能让Shiro对拿到雷姆的白丝充满信心。

输入格式

第一行两个正整数 $n,q$ 分别表示岛屿的数量和询问的数量。

接下来 $n$ 行，每行两个整数 $a_i,b_i$ 分别表示第 $i$ 座岛屿的劳累度和坚毅度。

接下来 $q$ 行，每行四个正整数 $l_i,r_i,c_i,d_i$ 分别表示区间左端点，区间右端点，初始劳累度与初始坚毅度。

输出格式

输出一共 $q$ 行，每行一个整数对应一个询问的答案。

样例 #1

样例输入 #1

4 2
1 1
4 2
5 1
2 7
1 4 6 5
2 4 3 3

样例输出 #1

2
1

样例 #2

样例输入 #2

20 10
215 144
2 110
174 132
214 142
116 108
155 192
236 208
216 214
99 220
236 118
190 81
230 131
10 238
189 198
183 13
45 193
14 234
208 192
126 19
49 38
7 14 251 184
2 18 89 76
11 15 49 196
8 11 83 139
10 15 119 239
9 16 148 120
11 17 225 34
15 16 3 46
14 15 86 227
7 18 252 103

样例输出 #2

7
2
2
2
1
3
1
1
0
7

提示

测试点 $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$。