012 - 回転マスゲーム

問題

イヅア高校の体育祭の呼び物は回転マスゲームです。このマスゲームでは、先生の号令に合わせて生徒達が回転して体の向きを変えます。生徒達が一糸乱れず動くのがカッコいいと評判です。

マスゲームに参加するN人の生徒には、1番からN番まで番号が付けられています。はじめ、N人の生徒が1番からN番まで番号順に、東から西に一列に並び、全員が北を向いて立ちます。先生は、何番から何番までの生徒がどれだけ回転するか指示を出します。先生がa,b,cと３つの数を叫ぶと、a番目からb番目までの生徒が、cの値に応じて一斉に回転して体の向きを変えます。cは整数で、正なら生徒が左回り、負なら生徒が右回りに、数の大きさ１ごとに４分の１回転します。たとえば、1なら左回りに４分の１回転、-2なら右回りに半回転、4なら左回りに1回転、-6なら右回りに1回転半回ります。

指示を出す役目の先生は、いくつかの時点での指示の直後で、指定した範囲の番号の生徒のうち北を向いている生徒の人数から南を向いている生徒の人数を引いた値が知りたいという問い合わせを校長先生からもらいました。号令の履歴のメモは手元にあるので、プログラムを書けばどの時点でも知りたい人数が割り出せるはずです。

先生の号令と校長先生からの問い合わせに関する情報が与えられたとき、各問い合わせについて北を向いている生徒の人数から南を向いている生徒の人数を引いた値を求めるプログラムを作成せよ。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$
$info_1$
$info_2$
 :
$info_M$

１行目にマスゲームに参加した生徒の人数 $N$ ( 1 ≤ $N$ ≤ 300 , 000 )、号令と問い合わせに関する情報の数 $M$ ( 1 ≤ $M$ ≤ 100 , 000 )が与えられる。続く $M$ 行に号令と問い合わせに関する情報 $info_i$ が与えられる。情報は時系列順に並んでいる。各 $info_i$ は、以下のいずれかの形式で与えられる。

1 $a$ $b$ $c$

または

2 $d$ $e$

1 $a$ $b$ $c$ は、 $a$ 番目から $b$ 番目までの生徒が数 $c$ に応じて回転せよという号令を表す。ただし、 1 ≤ $a$ ≤ $b$ ≤ $N$ 、 − 1 , 000 ≤ $c$ ≤ 1000 である。2 $d$ $e$ は、その直前の号令の直後に、 $d$ 番目から $e$ 番目までの生徒のうち北を向いている生徒の人数から南を向いている生徒の人数を引いた値がいくつになるかという問い合わせを表す。ただし、 1 ≤ $d$ ≤ $e$ ≤ $N$ である。

問い合わせに関する情報は１つ以上与えられる。

出力

各問い合わせについて、北を向いている生徒の人数から南を向いている生徒の人数を引いた値を1行に出力する。

入出力例

入力例

5 5
2 1 5
1 1 2 2
2 1 5
1 2 5 -1
2 1 5

出力例

5
1
-1