개뺑이

수직선 위에 로봇이 하나 있다. 로봇은 항상 정수 좌표에 위치한다.

총 $N$개의 유도 신호가 순서대로 주어진다. $i$번 유도 신호는 두 정수 $A_i,K_i$로 이루어져 있다.

로봇이 현재 좌표 $P$에 있을 때 $i$번 유도 신호를 받으면 다음 동작을 정확히 $K_i$번 반복한다.

• $P<A_i$이면 좌표 $P+1$로 이동한다.
• $P>A_i$이면 좌표 로 이동한다.

즉, 로봇은 매번 $A_i$를 향해 최대 한 칸 이동한다.

$Q$개의 독립적인 쿼리가 주어진다. 각 쿼리는 세 정수 $L,R,X$로 주어진다. 로봇을 처음 좌표 $X$에 놓은 뒤, $L$번부터 $R$번까지의 유도 신호를 순서대로 전달한다.

이 과정에서 로봇이 실제로 이동한 총거리를 구하여라. 각 쿼리는 서로 독립적이다.

입력은 다음과 같은 형식으로 주어진다.

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

각 쿼리마다 로봇이 실제로 이동한 총거리를 한 줄에 하나씩 출력한다.

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