P7470 [NOI Online 2021 Senior] Island Exploration

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.

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 $q$ lines in total, each containing one integer, the answer to the corresponding query.

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