Whitekingは地域の装飾ゲームをプレイしようとしている。彼が装飾したい領域は $N \times N$ のグリッド状になっており、単位グリッドは $1 \times 1$ の正方形タイルで表される。左上のタイルの座標は $(1, 1)$、右下のタイルの座標は $(N, N)$ である。したがって、タイルの座標は、そのタイルの右下隅の座標を指す。これより、$(x, y)$ に位置するタイルは $[x - 1, x] \times [y - 1, y]$ に対応する正方形領域を占有していることがわかる。各タイルは独自の美しさの値を持ち、初期状態ではすべてのタイルの美しさは 0 である。

この地域の装飾ゲームは、プレイヤーが以下の3つのアクションを用いてポイントを獲得するゲームである。

• 水平または垂直に直線を引くことで、グリッドを異なるゾーンに分割する。最初は $N \times N$ の領域が1つあるだけである。直線は両方向に無限に伸びる。例えば、水平に1本、垂直に1本直線を引くと、最初の領域は合計4つの領域に分割される。
• タイルを1つ選択し、そのタイルが属する領域を装飾する。その結果、装飾された領域内のすべてのタイルの美しさが、与えられた値だけ増加する。
• グリッド上の長方形を1つ選択し、その中にある最も美しいタイルの美しさに等しいポイントを獲得する。

Whitekingは、3番目のタイプのアクションごとに、自分が何ポイント獲得できるかを事前に知りたいと考えている。そのため、彼は実行する予定のアクションの順序付きリストをあなたに提示する。アクションは以下の形式で与えられる。

• “1 a b”: $a$ が 0 ならば直線 $x = b$ を引き、$a$ が 1 ならば直線 $y = b$ を引く。
• “2 a b X”: $(a, b)$ に位置するタイルを選択し、そのタイルが属する領域を装飾して、その領域内のすべてのタイルの美しさを $X$ だけ増加させる。
• “3 a b c d”: $(a, b)$ を左上のタイル、$(c, d)$ を右下のタイルとする長方形を選択し、その中にある最も美しいタイルの美しさに等しいポイントを獲得する。

Whitekingが3番目のタイプのアクションごとに獲得するスコアを求める手助けをせよ。

入力

最初の行には2つの整数 $N$ と $Q$ ($1 \le N \le 10^5$, $1 \le Q \le 3 \cdot 10^5$) が含まれる。 続く $Q$ 行の各行は、問題文で示された形式のアクションを記述する。

タイプ 1 のアクションについては、$0 \le a \le 1$ かつ $1 \le b \le N - 1$ である。 タイプ 2 のアクションについては、$1 \le a, b \le N$ かつ $-10^9 \le X \le 10^9$ である。 タイプ 3 のアクションについては、$1 \le a \le c \le N$ かつ $1 \le b \le d \le N$ である。

タイプ 2 のアクションは最大 25,000 回であり、タイプ 3 のアクションは少なくとも 1 回存在する。

出力

3番目のタイプのアクションごとに、Whitekingがそのアクションで獲得するスコアを出力せよ。

入出力例

入力 1

3 7
3 1 1 3 3
2 1 3 -3
3 1 1 3 3
1 0 1
2 1 1 4
3 2 2 3 3
3 1 1 3 3

出力 1

0
-3
-3
1