EGOI Buffet Infection Spread

Yesterday, $N$ customers visited the EGOI buffet. The customers are numbered from 1 to $N$. Customer i (for $1\le i\le N$) arrived at time $L_i$ and left at time $R_i$.

Today, it was discovered that one customer, who visited the restaurant, was infected with the new disease X which is now spreading in JOI country. The infectiousness of disease X is represented by an integer $x$. Specifically, for each customer $i$, if the cumulative total time during which customer $i$ is in the restaurant together with one or more infected customers reaches at least $x$, then customer $i$ becomes infected. Note that even if a customer becomes infected exactly when leaving the restaurant, he/she is still counted, and a customer once infected remains infected forever.

However, due to strict infection control measures in JOI country, the manager must determine the final number of infected customers. The twist is that both the identity of the infected customer (apart from the one initially infected) and the value of $x$ are not known in the investigation.

Thus, the manager decided to answer $Q$ queries. In the $j$-th query, the initially infected customer is $P_j$ and the infectiousness is $X_j$. Based on the information of the customers’ visit times, determine how many customers will finally be infected in each case.

Note: The overlapping time between a non‐infected customer and any infected customer while both are present in the restaurant accumulates continuously. The infection happens at the exact moment the cumulative overlapping time reaches $x$ (even if that moment coincides with a customer’s departure).

inputFormat

The first line contains two integers $N$ and $Q$, the number of customers and the number of queries.

Then $N$ lines follow. The $i$-th of these lines contains two integers $L_i$ and $R_i$, representing the arrival and departure times of customer $i$.

Then $Q$ lines follow. The $j$-th line contains two integers $P_j$ and $X_j$, meaning that in the $j$-th query, customer $P_j$ is initially infected and the infectiousness is $X_j$.

outputFormat

For each query, output the final number of infected customers on a separate line.

sample

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

3
1