ロボットの移動

数直線上にロボットが 1 台あり、ロボットは常に整数座標にいる。

$N$ 個の誘導信号が順番に与えられる。$i$ 番目の誘導信号は 2 つの整数 $A_i,K_i$ からなる。

ロボットが座標 $P$ にいるときに $i$ 番目の誘導信号を受けると、次の動作をちょうど $K_i$ 回繰り返す。

• $P<A_i$ なら座標 $P+1$ へ移動する。
• $P>A_i$ なら座標 へ移動する。

つまり、各回でロボットは $A_i$ に向かって高々 1 だけ移動する。

独立な $Q$ 個のクエリが与えられる。各クエリは 3 つの整数 $L,R,X$ からなる。ロボットを最初に座標 $X$ に置き、$L$ 番目から $R$ 番目までの誘導信号を順に与える。

この間にロボットが実際に移動した総距離を求めよ。各クエリは互いに独立である。

入力は次の形式で与えられる。

$N\ Q$ $A_1\ K_1$ $A_2$

各クエリについて、ロボットが実際に移動した総距離を 1 行に出力せよ。

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