PROGRAMMING:Portal
There are $$2n $$points on the plane, and their coordinates are $$(1,0), (2,0), \ \ cdots (n, 0) $$and $$(1,10 ^ 9), (2,10 ^ 9), \ \ cdots, (n, 10 ^ 9) $$. We call all the points with the coordinates of $$y $$0 $$as the "starting point" and all the points with the coordinates of $$y $$10 ^ 9 $$as the end point. A robot will start from the starting point with coordinates of $$(x, 0) $, and move in the positive direction of $$y $. Obviously, the robot will finally reach an end point. Let's set the $$x $$coordinate of the end point as $$f (x) $.
Under the above conditions, there is obviously $$f (x) = x $$. However, such a mathematical model is too boring, so we make some small changes to the above mathematical model. We will make $$q $$modifications to the model. Each modification is one of the following two operations:
*\ + $$X '$$$X' '$$$y $$: add a pair of gateways at $$(x', y) $$and $$(x '', y) $. When the robot touches one of the gateways, it is immediately transferred to the other. Data guarantees that there is no portal at $$(x ', y) $$and $$(x' ', y) $.
*\ - $$X '$$$X' '$$$y $$: remove a pair of portals at $$(x', y) $$and $$(x '', y) $. The data guarantees that this pair of gateways exists.
After each modification, calculate the $$\ sum / limits_{ X = 1} ^ n XF (x) $.
###Input format:
In the first line, enter two integers, $$n $$and $$q $$($$2 / Le n / Le 10 ^ 5 $$, $$1 / Le Q / Le 10 ^ 5 $$), representing the number of start and end points and the number of modifications.
Next, on line $$q $, enter the character $$op on line $$I $_ I $$and three integers $$X '_ i$$, $$x''_ i$$ and $$y_ i$$ ($$op_ i \in \{\text{`+' (ascii: 43)}, \text{`-' (ascii: 45)}\}$$, $$1 \le x'_ i < x''_ i \le n$$, $$1 \le y_ I < 10 ^ 9 $$), which represents the content of the $$I $$. The order of modification is the same as that of input.
###Output format:
Output the $$q $$line, where the $$I $$line contains an integer to represent the $$I $$modified answer.
###Input example:
```in
5 4
+ 1 3 1
+ 1 4 3
+ 2 5 2
- 1 4 3
```
###Output example:
```out
fifty-one
forty-eight
thirty-nine
forty-two
```
###Example explanation:
Modify the result of | $$f (1) $$$f (2) $$$f (3) $$$$f (4) $$$f (5) $$
--- | ---
\+ 1 3 1 | 3 | 2 | 1 | 4 | 5 | 51
\+ 1 4 3 | 3 | 2 | 4 | 1 | 5 | 48
\+ 2 5 2 | 3 | 5 | 4 | 1 | 2 | 39
\- 1 4 3 | 3 | 5 | 1 | 4 | 2 | 42
answer：If there is no answer, please comment
Assuming that this question only needs to output the answer once after all the modifications are completed, we can find that the essence of "adding a pair of gateways" is "exchanging two numbers". Note that the order between the different exchange operations is critical. The larger the $$y $$of the exchange operation is, the earlier the operation is performed. Since the existing portal will not be covered when adding a portal, the same exchange operations of $$y $$will not affect each other, and can be sorted arbitrarily (for example, $$y $$can be sorted as the first keyword and $$X '$$as the second keyword). After executing the whole operation sequence, you can get the answer.
For small-scale data, you can maintain "what operations have appeared" before each query, and then perform these operations in order. The order of operations needs to be sorted, so the overall complexity is $$o (n ^ 2logn) $.
Note that this problem does not require online results, then the relative position of an operation in all operations is known. We can read in all the input and sort all the operations. At this time, we only need to divide the operation sequence into blocks and maintain the execution results in each block. When adding / deleting an operation, we only need to modify the internal results of the block in which the operation is located, and then combine the results of each block to get the final answer. Complexity $$o (n / sqrt {n}) $.
Under the above conditions, there is obviously $$f (x) = x $$. However, such a mathematical model is too boring, so we make some small changes to the above mathematical model. We will make $$q $$modifications to the model. Each modification is one of the following two operations:
*\ + $$X '$$$X' '$$$y $$: add a pair of gateways at $$(x', y) $$and $$(x '', y) $. When the robot touches one of the gateways, it is immediately transferred to the other. Data guarantees that there is no portal at $$(x ', y) $$and $$(x' ', y) $.
*\ - $$X '$$$X' '$$$y $$: remove a pair of portals at $$(x', y) $$and $$(x '', y) $. The data guarantees that this pair of gateways exists.
After each modification, calculate the $$\ sum / limits_{ X = 1} ^ n XF (x) $.
###Input format:
In the first line, enter two integers, $$n $$and $$q $$($$2 / Le n / Le 10 ^ 5 $$, $$1 / Le Q / Le 10 ^ 5 $$), representing the number of start and end points and the number of modifications.
Next, on line $$q $, enter the character $$op on line $$I $_ I $$and three integers $$X '_ i$$, $$x''_ i$$ and $$y_ i$$ ($$op_ i \in \{\text{`+' (ascii: 43)}, \text{`-' (ascii: 45)}\}$$, $$1 \le x'_ i < x''_ i \le n$$, $$1 \le y_ I < 10 ^ 9 $$), which represents the content of the $$I $$. The order of modification is the same as that of input.
###Output format:
Output the $$q $$line, where the $$I $$line contains an integer to represent the $$I $$modified answer.
###Input example:
```in
5 4
+ 1 3 1
+ 1 4 3
+ 2 5 2
- 1 4 3
```
###Output example:
```out
fifty-one
forty-eight
thirty-nine
forty-two
```
###Example explanation:
Modify the result of | $$f (1) $$$f (2) $$$f (3) $$$$f (4) $$$f (5) $$
--- | ---
\+ 1 3 1 | 3 | 2 | 1 | 4 | 5 | 51
\+ 1 4 3 | 3 | 2 | 4 | 1 | 5 | 48
\+ 2 5 2 | 3 | 5 | 4 | 1 | 2 | 39
\- 1 4 3 | 3 | 5 | 1 | 4 | 2 | 42
answer：If there is no answer, please comment
Assuming that this question only needs to output the answer once after all the modifications are completed, we can find that the essence of "adding a pair of gateways" is "exchanging two numbers". Note that the order between the different exchange operations is critical. The larger the $$y $$of the exchange operation is, the earlier the operation is performed. Since the existing portal will not be covered when adding a portal, the same exchange operations of $$y $$will not affect each other, and can be sorted arbitrarily (for example, $$y $$can be sorted as the first keyword and $$X '$$as the second keyword). After executing the whole operation sequence, you can get the answer.
For small-scale data, you can maintain "what operations have appeared" before each query, and then perform these operations in order. The order of operations needs to be sorted, so the overall complexity is $$o (n ^ 2logn) $.
Note that this problem does not require online results, then the relative position of an operation in all operations is known. We can read in all the input and sort all the operations. At this time, we only need to divide the operation sequence into blocks and maintain the execution results in each block. When adding / deleting an operation, we only need to modify the internal results of the block in which the operation is located, and then combine the results of each block to get the final answer. Complexity $$o (n / sqrt {n}) $.