AT_otemae2019_e 最悪の教頭 (Worst Head Teacher)

[problemUrl]: https://atcoder.jp/contests/otemae2019/tasks/otemae2019_e 時は $ 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 $ 個の質問の情報が与えられるので，それぞれの質問ごとに，条件を満たす参加者の人数を求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる． > $ N $ $ Q $ $ D_1 $ $ \vdots $ $ D_N $ $ T_1 $ $ L_1 $ $ R_1 $ $ \vdots $ $ T_Q $ $ L_Q $ $ R_Q $

標準出力に $ Q $ 行で出力せよ．$ j $ 行目 $ (1\ \leq\ j\ \leq\ Q) $ には，$ j $ 個目の質問の答えを表す整数を出力せよ．

### 制約 - 入力はすべて整数である． - $ 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 $ 点) 追加の制約はない． ### Sample Explanation 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 $にいる．