Problem Description

Songmu is a girl who likes adventures. One day, she came to a sea area to explore.

In this sea area, there are $n$ islands in a row, numbered $1,2,3,\ldots,n$. Each island has two values: fatigue $a_i$ and fun $b_i$.

For an island with fatigue $a$ and fun $b$, if this island satisfies $(a\oplus c) \leq \min(b,d)$, then Songmu will feel happy when exploring this island. Here, $c$ denotes Songmu's fatigue before going onto the island (called the initial fatigue), and similarly, $d$ denotes Songmu's initial fun. $\oplus$ denotes bitwise XOR (i.e., addition without carry in binary).

To enjoy herself more, Songmu will ask you $q$ queries. Each query gives an interval $[l_i,r_i]$ and two numbers $c_i,d_i$. You need to tell Songmu: if her initial fatigue is $c_i$ and her initial fun is $d_i$, then how many islands with indices in the interval $[l_i,r_i]$ can make Songmu feel happy while exploring.

Input Format

The first line contains two positive integers $n,q$, denoting the number of islands and the number of queries.

The next $n$ lines each contain two integers $a_i,b_i$, denoting the fatigue and fun of the $i$-th island.

The next $q$ lines each contain four positive integers $l_i,r_i,c_i,d_i$, denoting the left endpoint of the interval, the right endpoint of the interval, the initial fatigue, and the initial fun.

Output Format

Output $q$ lines in total, each containing one integer, the answer to the corresponding query.

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

Hint

Test points $1,2$ satisfy $1\leq n,q\leq 5000$.

Test points $3,4$ satisfy $1\leq n,q\leq 10^4$.

Test points $5,6,7$ satisfy $1\leq n,q\leq 10^5$ and $\max\{d_i\}\leq \min\{b_i\}$.

Test points $8,9,10,11$ satisfy $1\leq n,q\leq 10^5$ and $\min\{d_i\}\geq \max\{b_i\}$.

Test points $12,13$ satisfy $1\leq n,q\leq 10^5$ and $l_i=1,r_i=n$.

Test points $14,15,16$ satisfy $1\leq n,q\leq 7\times 10^4$.

Test points $17,18,19,20$ satisfy $1\leq n,q\leq 10^5$.

All testdata satisfy $1\leq n,q\leq 10^5$, $1\leq a_i,b_i,c_i,d_i\leq 2^{24}-1$.

Translated by ChatGPT 5