問題

時は 22 世紀，新たに大手前高校の校長となったピ太郎の尽力により，大手前プロコンは世界中から注目されるイベントとなっていた．

大手前プロコン 21XX の開会式では，N 人の生徒が一列に並んで行進する．生徒が進む道は数直線としてあらわされる．生徒たちは全員，数直線上の正の方向を向いて行進する．時刻 0 に，前から i 番目 (1 \leq i \leq N) の生徒は，座標 −i に立っている．座標 0 には，旗手のピ太郎校長が立っている．

ピ太郎校長は，単位時刻あたり 1 だけ道の上を正の方向に進む．

すべての生徒には呑気さという値が定まっている．前から i 番目の生徒の呑気さは D_i である．各生徒は単位時間かけて同時に以下の行動を取る．

• 時刻 0 に前から i 番目にいた生徒は，時刻 0 に自分の目の前にいた参加者 (生徒またはピ太郎校長) との距離がちょうど D_i なら，距離 1 だけ 道の上を正の方向に進む．そうでないなら，動かない．

あなたは，開会式を見に来たきたむー教頭である．あなたは写真を撮らなければならなかったが，開会式の間中ずっと熟睡していた．仕方がないので，あなたは会場の写真を撮り，その写真に参加者の絵を描いて誤魔化すことにした．

誤魔化したことを明るみに出さないために，また絵を描く手間を見積もるために，あなたは以下の Q 個の値を知っておきたい．

• 時刻 T_j における，L_j 以上 R_j 以下の座標に立っている参加者の人数 (1 \leq j \leq Q)

各生徒の呑気さと，Q 個の質問の情報が与えられるので，それぞれの質問ごとに，条件を満たす参加者の人数を求めるプログラムを作成せよ．

制約

• 入力はすべて整数である．
• 1 \leq N \leq 500\,000．
• 1 \leq Q \leq 500\,000．
• 1 \leq D_i \leq 1\,000\,000\,000 (1 \leq i \leq N)．
• 1 \leq T_j \leq 1\,000\,000\,000 (1 \leq j \leq Q)．
• 1 \leq L_j \leq R_j \leq 1\,000\,000\,000 (1 \leq j \leq Q)．

小課題

1. (15 点) N, Q, D_i, T_j, L_j, R_j \leq 1\,000 (1 \leq i \leq N, 1 \leq j \leq Q)．
2. (16 点) T_i = T_j (1 \leq i,j \leq Q)．
3. (69 点) 追加の制約はない．

入力例 1

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

出力例 1

0
1
1
2
1
1

時刻 0 には，校長，選手 1，2，3 の順に，それぞれ座標 0,-1,-2,-3 にいる．

時刻 1 にはそれぞれ，座標 1,-1,-2,-3 にいる．

時刻 2 にはそれぞれ，座標 2,0,-2,-3 にいる．これは時刻 1 から時刻 2 にかけて，それぞれ次のような行動を取ったからである．

• 校長は場所 2 に移動する
• 選手 1 は前の参加者との差が 2 になったから場所 0 に移動する
• 選手 2 は前の参加者との差が 5 未満だから動かない
• 選手 3 は前の参加者との差が 3 未満だから動かない

時刻 3 にはそれぞれ，座標 3,1,-2,-3にいる．

入力例 2

4 2
1
1
1
1
2 1 4
1 3 6

出力例 2

2
0

入力例 3

6 6
11
36
28
80
98
66
36 29 33
190 171 210
18 20 100
1000 900 1100
92 87 99
200 100 300

出力例 3

0
2
0
4
1
4