Robot Travel

A robot is on a number line and is always located at an integer coordinate.

There are $N$ guidance signals in order. The $i$-th signal consists of two integers $A_i,K_i$.

When the robot is at coordinate $P$ and receives the $i$-th signal, it repeats the following action exactly $K_i$ times.

• If $P<A_i$, move to $P+1$.
• If $P>A_i$, move to .

Thus, at each repetition, the robot moves by at most one unit toward $A_i$.

You are given $Q$ independent queries. Each query consists of three integers $L,R,X$. Place the robot initially at coordinate $X$, then apply signals $L$ through $R$ in order.

Find the total distance that the robot actually moves during this process. The queries are independent of each other.

The input is given in the following format.

$N\ Q$ $A_1\ K_1$ $A_{}$

For each query, print the total distance actually traveled by the robot on its own line.

• $1 \le N,Q \le 200\,000$.
• $-10^9 \le A_i \le 10^9$ ().