题目描述

小女孩奥莉娅是完美人类的典范：她每天都解题。然而，在家学习几乎不可能，因为她家里住着一只调皮的猫康斯坦丁，它总会找机会搞破坏。

生日时，奥莉娅收到了一大块白色笛卡尔平面作为草稿纸。康斯坦丁立刻想把这个漂亮的礼物弄坏。

这块平面是一个白色正方形，左下角坐标为 $(0,0)$，右上角坐标为 $(N,N)$。为了方便，奥莉娅在平面的四个角，即 $(0,0)$、$(N,0)$、$(0,N)$、$(N,N)$，各放了一瓶墨水，然后坐下来写一场复杂的比赛。

当奥莉娅正在写题时，康斯坦丁可能走过去“偶然”打翻任意一瓶墨水。此时，以该墨水瓶所在角和点 $(x,y)$ 为对角的矩形区域会被彻底弄脏，并全部染成黑色。奥莉娅当然会喊几声，但也只能重新装满墨水瓶继续写比赛。之后康斯坦丁还可以再次打翻墨水，染黑另一个区域。

有时，奥莉娅遇到特别困难的题目，会决定在平面的某个区域记录想法。她总是选择一个边与坐标轴平行的矩形区域。显然，她需要知道所选区域中有多少面积已经被墨水覆盖。奥莉娅忙于解题，所以需要你来帮助她。

任务

请根据比赛期间发生的事件，帮助奥莉娅求出查询矩形中被猫弄脏的面积。

输入格式

第一行包含两个整数 $N,Q$（$1 \le N,Q \le 10^5$），分别表示平面的边长和事件数量。

接下来 $Q$ 行描述事件。每行首先包含一个整数 $t$。

若 $1 \le t \le 4$，表示康斯坦丁打翻了对应角落的墨水瓶。此时接下来给出两个整数 $x,y$（$0 \le x,y \le N$），表示被染黑矩形区域的另一个对角点。

四个墨水瓶的位置如下：

1. 左下角；
2. 右下角；
3. 左上角；
4. 右上角。

若 $t=0$，接下来给出四个整数 $x_1,y_1,x_2,y_2$（$0 \le x_1<x_2\le N$，$0 \le y_1<y_2\le N$），表示奥莉娅选择的查询矩形，其对角点为 $(x_1,y_1)$ 与 $(x_2,y_2)$。

保证输入中至少有一个 $t=0$ 的事件，且猫染黑的矩形面积非零。

输出格式

对于每个类型 $0$ 的查询，按输入顺序输出一行一个整数，表示对应矩形中被猫弄脏的面积。

输入

8 5
1 2 4
2 0 1
3 3 3
4 6 6
0 1 2 7 7

输出

10

子任务

1.（5 分）$1 \le N,Q \le 100$；

2.（6 分）$1 \le N,Q \le 1000$，$t \in \{0,1,2\}$；

3.（8 分）$1 \le N,Q \le 1000$；

4.（14 分）$1 \le N,Q \le 50000$，类型 $0$ 的查询数 量不超过 $20$；

5.（12 分）$1 \le N,Q \le 50000$，$t \in \{0,1\}$， 且对所有类型 $1$ 的染色事件，若事件 $a$ 晚于事件 $b$， 则 $x_a \le x_b$ 且 $y_a \ge y_b$；

6.（8 分）$1 \le N,Q \le 50000$，$t \in \{0,1\}$；

7.（10 分）$1 \le N,Q \le 50000$，$t \in \{0,1,2\}$；

8.（13 分）$1 \le N,Q \le 50000$；

9.（9 分）$t \in \{0,1\}$；

10.（8 分）$t \in \{0,1,2\}$； 11.（7 分）无额外限制。