AT_past18_o 蟻の移動

$ 1 $ から $ N $ までの番号が付けられた $ N $ 匹の蟻が数直線上に並んでいます。 この数直線上では右に行くほど座標が大きくなります。 **初期状態**において、蟻 $ i $ は初期座標 $ X_i $ におり、向いている向きは文字 $ D_i $ によって表されます。 具体的には、 $ D_i= $ `R` のとき右を、 $ D_i= $ `L` のとき左を向いています。 ここで、 $ X_1,X_2,\dots,X_N $ はすべて偶数であり、互いに相異なることが保証されます。 すぬけくんが指を鳴らすと、蟻たちは以下の規則に従って動き始めます。 - それぞれの蟻は、自分が向いている方向に向かって秒速 $ 1 $ で数直線上を移動する。 - $ 2 $ 匹の蟻が同時にある座標に到達した場合は、それぞれの蟻が向きを反対方向に変えて移動を続ける。これを蟻の**衝突**とよぶ。 なお、 $ 3 $ 匹以上の蟻が同時にある座標に到達することはないことが証明できる。 以下のいずれかの形式のクエリが合わせて $ Q $ 個与えられるので、順番に処理してください。 - `1 x d` : 初期座標が $ x $ 、向いている向きが文字 $ d $ で表されるような蟻を初期状態に追加する。 ここで、 $ x $ は偶数であり、既に存在するどの蟻の初期座標とも一致しないことが保証される。 - `2 l r` : 現在の初期状態において時刻 $ 0 $ にすぬけくんが指を鳴らした場合に、蟻 $ 1 $ と他の蟻との衝突が起こる時刻を早い順に $ t_1,t_2,\dots $ とする。 $ t_{l}+t_{l+1}+\dots +t_{r} $ を求め、出力する。 ただし、 $ l \leq r $ 、および蟻 $ 1 $ と他の蟻との衝突は $ r $ 回以上起こることが保証される。 なお、 $ 2 $ 種類目のクエリは独立であることに注意してください。 すなわち、 $ 2 $ 種類目のクエリを処理することで、蟻たちの初期状態が変わることはありません。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ X_1 $ $ D_1 $ $ X_2 $ $ D_2 $ $ \vdots $ $ X_N $ $ D_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ ここで、 $ \mathrm{query}_i $ は $ i $ 番目のクエリを表し、以下のいずれかの形式である。 > $ 1 $ $ x $ $ d $ > $ 2 $ $ l $ $ r $

$ 2 $ 種類目のクエリの数を $ T $ としたとき、 $ T $ 行出力せよ。 $ i\ (1\leq i \leq T) $ 行目には、 $ 2 $ 種類目のクエリのうち $ i $ 番目のものに対する答えを整数として出力せよ。

### Sample Explanation 1 クエリを処理する前の段階での初期状態においてすぬけくんが指を鳴らした場合、蟻たちは以下のように行動します。 - 時刻 $ 0 $ にすべての蟻が移動を始める。それぞれの蟻が向いている向きは右、左である。 - 時刻 $ 4\ (:=t_1) $ に座標 $ 6 $ で蟻 $ 1,2 $ が衝突する。それぞれの蟻が向いている向きは左、右になる。 よって、 $ 1 $ 番目のクエリに対する答えは $ t_1=4 $ です。 $ 3 $ 番目のクエリまで処理した段階での初期状態においてすぬけくんが指を鳴らした場合、蟻たちは以下のように行動します。 ただし、 $ 2,3 $ 番目のクエリで追加された蟻の番号をそれぞれ $ 3,4 $ とします。 - 時刻 $ 0 $ にすべての蟻が移動を始める。それぞれの蟻が向いている向きは右、左、左、右である。 - 時刻 $ 1 $ に座標 $ -1 $ で蟻 $ 3,4 $ が衝突する。それぞれの蟻が向いている向きは右、左、右、左になる。 - 時刻 $ 4\ (:=t_1) $ に座標 $ 6 $ で蟻 $ 1,2 $ が衝突する。それぞれの蟻が向いている向きは左、右、右、左になる。 - 時刻 $ 6\ (:=t_2) $ に座標 $ 4 $ で蟻 $ 1,3 $ が衝突する。それぞれの蟻が向いている向きは右、右、左、左になる。 よって、 $ 4 $ 番目のクエリに対する答えは $ t_1+t_2=10 $ 、 $ 5 $ 番目のクエリに対する答えは $ t_2=6 $ です。 ### Constraints - $ N,Q $ は整数 - $ 1\leq N,Q \leq 10^5 $ - $ X_i $ は偶数 - $ |X_i| \leq 10^9 $ - $ X_i \neq X_j\ (i \neq j) $ - $ D_i $ は `R` または `L` - $ 1 $ 種類目のクエリにおいて、 - $ x $ は偶数 - $ |x| \leq 10^9 $ - そのクエリの段階において、初期座標が $ x $ であるような蟻は存在しない - $ d $ は `R` または `L` - $ 2 $ 種類目のクエリにおいて、 - $ l,r $ は整数 - $ 1 \leq l \leq r \leq M $ ただし $ M $ はそのクエリの段階での初期状態においてすぬけくんが指を鳴らした場合に蟻 $ 1 $ と他の蟻との衝突が起こる回数