Olya and the Plane
Olya is an exemplary problem solver, tackling challenges daily. However, working from home is a struggle because her playful cat, Kostyantyn, is always ready to cause chaos. When Olya received a large white Cartesian plane for her birthday, Kostyantyn immediately saw it as an opportunity to create mischief.
The plane is a white square with its bottom-left corner at (0, 0) and top-right corner at (N, N). To make things easier, Olya placed an ink bottle at each corner of the plane: (0, 0), (N, 0), (0, N), and (N, N). She then sat down to write a complex contest.
As Olya works, Kostyantyn might "accidentally" tip over any ink bottle, causing the rectangular area between the bottle's location and a point (x, y) on the plane to be completely covered in ink. Despite her frustration, Olya refills the bottle and continues her work, while Kostyantyn might spill ink again, covering another section of the plane.
When Olya faces a particularly tough problem, she writes down her thoughts on a rectangular section of the plane, always choosing an area parallel to the coordinate axes. To do this efficiently, she needs to know how much of the selected area is already ink-covered. Since she's busy solving problems, she needs your help to determine this.
Task
Create a program that helps Olya calculate the ink-covered area of the plane based on the events that occur during the contest.
Input Data
The first line of input contains two integers N and Q (1 ≤ N,Q ≤ 10^5), representing the size of the plane and the number of events during the contest, respectively.
The following Q lines describe the events. Each line starts with an integer t, indicating the type of event. If 1 ≤ t ≤ 4, it means Kostyantyn has knocked over the corresponding ink bottle. Two integers x and y (0 ≤ x,y ≤ N) follow, specifying the opposite corner of the area that will be inked.
The ink bottles are located as follows: the first at the bottom-left, the second at the bottom-right, the third at the top-left, and the fourth at the top-right corners.
If t equals 0, four integers x1, y1, x2, y2, (0 ≤ x1 < x2 ≤ N, 0 ≤ y1 < y2 ≤ N) follow, defining a rectangle parallel to the coordinate axes with opposite corners at (x1, y1) and (x2, y2).
It is guaranteed that there is at least one event of type 0 in the input, and the cat only spills ink over areas with non-zero size.
Output Data
For each query of type 0, output a single integer on a separate line, representing the area of the specified section of the plane that has been inked by the cat. Provide the answers in the order the queries appear in the input.
Evaluation
Subtask Points Additional Constraints Required Subtasks
0 0 Tests from the condition -
1 5 1 ≤ N,Q ≤ 100 0
2 6 1 ≤ N,Q ≤ 1000, t ∈ {0, 1, 2} -
3 8 1 ≤ N,Q ≤ 1000 0, 1, 2
4 14 1 ≤ N,Q ≤ 50000, number of zero-type queries not more than 20 0
5 12 1 ≤ N,Q ≤ 50000, t ∈ {0, 1}, for all first-type queries -condition holds: if query a comes later than query b, thenxa ≤ xb, ya ≥ yb
6 8 1 ≤ N,Q ≤ 50000, t ∈ {0, 1} -
7 10 1 ≤ N,Q ≤ 50000, t ∈ {0, 1, 2} 2, 5, 6
8 13 1 ≤ N,Q ≤ 50000 0, 1, 2, 3, 4, 5, 6, 7
9 9 t ∈ {0, 1} 5, 6
10 8 t ∈ {0, 1, 2} 2, 5, 6, 7, 9
11 7 No additional constraints 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
