题目描述

凇睦是一个喜欢探险的女孩子，这天她到一片海域上来探险了。

在这片海域上一共有 $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]$ 这个区间内的岛屿能使凇睦探险时感到开心。

输入格式

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

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

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

输出格式

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

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

2
1

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

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$。