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$ 行中，每一行描述一个如题目所述格式的操作。

对于类型 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 次。

输出格式

对于每一次第三种操作，输出 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