C. Gardening Game
time limit per test
15 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

Whiteking is going to play a local decorating game. The area he wants to decorate is in the form of an $$$N \times N$$$ grid in which the unit grid is represented by $$$1 \times 1$$$ square tiles, the coordinates of the top left tile are $$$(1, 1)$$$, and the coordinates of the bottom right tile are $$$(N, N)$$$. Thus the coordinates of the tile refer to the coordinates of the lower right corner of the tile. From this, it can be seen that the tile located at $$$(x, y)$$$ occupies a square area corresponding to $$$[x-1, x] \times [y-1, y]$$$. Each tile has its own beauty value, initially all tiles have a beauty value of $$$0$$$.

The local decorating game is a game where the player earns points using the following three actions.

  • Divide the grid into different zones by drawing a straight line horizontally or vertically. Initially, there is only one area of size $$$N \times N$$$. The lines are infinite in both directions: for example, if you draw a straight line horizontally and another one vertically, the initial area will be divided into a total of four areas.
  • Select a tile and decorate the area it belongs to. As a result, the beauty of all tiles in the decorated area is increased by a given value.
  • Select a rectangle on the grid and earn points equal to the beauty of the most beautiful tile in it.

Whiteking wants to know in advance how many points he will earn for every action of the third type. So he will show you an ordered list of actions he is going to perform. The actions will be given in the following format:

  • "1 $$$a$$$ $$$b$$$": If $$$a$$$ is $$$0$$$, draw the straight line $$$x = b$$$, and if $$$a$$$ is $$$1$$$, draw $$$y = b$$$.
  • "2 $$$a$$$ $$$b$$$ $$$X$$$": Select the tile located at $$$(a, b)$$$ decorate the area it belongs to, increasing the beauty of all tiles in it by $$$X$$$.
  • "3 $$$a$$$ $$$b$$$ $$$c$$$ $$$d$$$": Select a rectangle with $$$(a, b)$$$ as the top left tile and $$$(c, d)$$$ as the bottom right tile, and earn points equal to the beauty of the most beautiful tile in it.

Help Whiteking find what will be the score for every action of the third type.

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le Q \le 3 \cdot 10^5$$$).

Each of the next $$$Q$$$ lines describes an action in the format shown in the problem statement.

For an action of type 1, $$$0 \le a \le 1$$$ and $$$1 \le b \le N - 1$$$.

For an action of type 2, $$$1 \le a, b \le N$$$ and $$$-10^9 \le X \le 10^9$$$.

For an action of type 3, $$$1 \le a \le c \le N$$$ and $$$1 \le b \le d \le N$$$.

There are at most $$$25\,000$$$ actions of type $$$2$$$, and at least $$$1$$$ action of type $$$3$$$.

Output

For every action of the third type, print the score that Whiteking will get for that action.

Example
Input
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
Output
0
-3
-3
1