Whiteking 準備玩一個區域裝飾遊戲。他想要裝飾的區域是一個 $N \times N$ 的網格，其中單位網格由 $1 \times 1$ 的方塊組成，左上角方塊的座標為 $(1, 1)$，右下角方塊的座標為 $(N, N)$。因此，方塊的座標是指該方塊右下角的座標。由此可知，位於 $(x, y)$ 的方塊佔據了 $[x - 1, x] \times [y - 1, y]$ 的正方形區域。每個方塊都有其自身的「美感值」，初始時所有方塊的美感值均為 0。

這個區域裝飾遊戲中，玩家可以透過以下三種動作來獲得分數：

• 透過繪製水平或垂直的直線將網格劃分為不同的區域。最初，只有一個大小為 $N \times N$ 的區域。這些線在兩個方向上都是無限延伸的：例如，如果你畫一條水平線和一條垂直線，初始區域將被劃分為總共四個區域。
• 選擇一個方塊並裝飾它所屬的區域。結果是，該區域內所有方塊的美感值都會增加一個給定的數值。
• 選擇網格上的一個矩形，並獲得等於該矩形內最美方塊美感值的分數。

Whiteking 想要預先知道他對於每一種第三類動作將獲得多少分數。因此，他會向你展示他將要執行的一系列有序動作。動作將以以下格式給出：

• “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 計算出他對於每一個第三類動作將獲得的分數。

輸入格式

第一行包含兩個整數 $N$ 和 $Q$ ($1 \le N \le 10^5$, $1 \le Q \le 3 \cdot 10^5$)。

接下來的 $Q$ 行，每一行描述一個如題目敘述中所述格式的動作。

對於第一類動作，$0 \le a \le 1$ 且 $1 \le b \le N - 1$。 對於第二類動作，$1 \le a, b \le N$ 且 $-10^9 \le X \le 10^9$。 對於第三類動作，$1 \le a \le c \le N$ 且 $1 \le b \le d \le N$。

其中第二類動作最多有 25,000 個，且至少有 1 個第三類動作。

輸出格式

對於每一個第三類動作，輸出 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