Problem Description

In a certain country, there are $ N $ cities numbered from city $ 1 $ to city $ N $.
There are $ N - 1 $ roads in this country, and each road is dangerous and has an age limit. The $ i $-th road connects city $ i $ and city $ i + 1 $ bidirectionally and can be used by people aged $ L_i $ or older and $ R_i $ or younger.
You have started a travel agency in this country. Answer $ Q $ queries from customers.
In the $ i $-th query, you are given $ A_i $ and $ B_i $. Determine the number of cities (including city $ B_i $ itself) that a person aged $ A_i $ can visit starting from city $ B_i $ by following the roads. The age of this person does not change during the trip.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ L_3 $ $ R_3 $ $\hspace{15pt}\ \vdots$ $ L_{N - 1} $ $ R_{N - 1} $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ A_3 $ $ B_3 $ $\hspace{15pt}\ \vdots$ $ A_Q $ $ B_Q $

Output Format

Output $ Q $ lines, where the $ i $-th line contains the answer to the $ i $-th query.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3
3
2

Sample Input #2

6 3
4 7
3 8
1 6
5 9
7 10
5 1
7 6
4 6

Sample Output #2

5
3
1

Notes/Hints

Constraints

• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $1 \le L_i \le R_i \le 10^9$
• $1 \le A_i \le 10^9$
• $1 \le B_i \le N$
• All inputs are integers

Sample Explanation 1

In the first query, a person aged $ 3 $ starts traveling from city $ 1 $. They can travel through all roads except the third one, so they can reach cities $ 1 $ to $ 3 $, totaling $ 3 $ cities. In the second query, a person aged $ 2 $ starts traveling from city $ 2 $. They can travel through all roads except the first one, so they can reach cities $ 2 $ to $ 4 $, totaling $ 3 $ cities. In the third query, a person aged $ 1 $ starts traveling from city $ 4 $. They can only travel through the third road, so they can reach cities $ 3 $ and $ 4 $, totaling $ 2 $ cities.

见题面 Input 部分

见题面 Output 部分