Racing on Pandora

On the planet Pandora, a unique race is underway. There are \(n\) cars running on a long straight track with coordinates measured in meters. Each car moves at a constant speed of \(1\) meter per second.

The \(i\)th car starts at coordinate \(a_i\) at time \(0\) and moves towards \(b_i\). When it reaches \(b_i\), it reverses the direction and heads back to \(a_i\), repeating this back-and-forth movement continuously. The movement of each car can be described mathematically as follows:

[ L_i = |b_i - a_i|, \quad t' = t \bmod (2L_i), ]

[ \text{position}_i(t) = \begin{cases} a_i + \mathrm{sgn}(b_i-a_i) \cdot t', & \text{if } t' < L_i,\ b_i - \mathrm{sgn}(b_i-a_i) \cdot (t' - L_i), & \text{if } t' \ge L_i, \end{cases} ]

Note that if \(a_i = b_i\), the car remains at that point for all time.

Handsome Mike intends to disrupt the race by placing dynamite and has \(m\) queries. The \(j\)th query consists of a time \(t_j\) and a track interval \([x_j, y_j]\). For each query, you must determine the number of cars whose positions at time \(t_j\) fall within the interval \([x_j, y_j]\) (inclusive).

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n, m \leq 10^5)\) — the number of cars and the number of queries.

The next \(n\) lines each contain two integers \(a_i\) and \(b_i\) \( (-10^9 \le a_i, b_i \le 10^9)\) representing the two end points of the route for the \(i\)th car.

The following \(m\) lines each contain three integers \(t_j, x_j, y_j\) \( (0 \leq t_j \leq 10^9, -10^9 \le x_j \le y_j \le 10^9)\) representing a query: after \(t_j\) seconds, count how many cars are located in the interval \([x_j, y_j]\).

outputFormat

For each query, output a single integer — the number of cars whose position at the given time is within the specified interval.

sample

3 3
0 10
5 15
10 0
5 0 10
10 5 15
20 0 5

3
2
2