405310: GYM101879 G Running a penitentiary

The penitentiary at Viana do Castelo is one of the largest ones in Europe. The building has thousands of jail cells, laid out linearly in several levels, and numbered so that adjacent numbers are given to adjacent cells, be it adjacent cells on the same level, or one on top of the other, or connected by an adjacent stairway. It is not really known why, but the jail cells are numbered starting from a negative number, so that cell number zero is right in the middle of the penitentiary, exactly at the center of the middle level of the building. Probably the first warden, who assigned the cells numbering, did this for entertainment $$$\ldots$$$

Each guard in the penitentiary gets an interval of cells to watch. He must go over these cells and check that the inmates did not escape, are doing okay, and so on. The warden does two operations depending on the intervals of cells assigned to each guard:

1. Given a guard $$$i$$$, change the interval of cells assigned to him to $$$[\ell,r]$$$;
2. Given an interval of guards $$$[a,b]$$$, find how many cells are watched by all the guards in this interval at the moment.

Your task in this problem is to read the number $$$N$$$ of guards in the penitentiary and, for each guard, the interval of cells he is in charge of watching over. Next, you will read the $$$Q$$$ operations carried out by the warden, by executing an operation of the first type or by answering the query for operations of the second type.

The first line has two integers $$$N$$$ and $$$Q$$$, the number of guards and the number of operations to carry out, respectively. The next $$$N$$$ lines describe the guards information. The $$$i$$$th of these lines has two integers, $$$L_i$$$ and $$$R_i$$$, the interval of cells assigned to the $$$i$$$th guard. Finally, the next $$$Q$$$ lines describe the operations chosen by the warden. Each one of these lines represents an operation as follows

• "C$$$\ i \ \ell \ r$$$": this indicates changing the interval of cells of the $$$i$$$th guard to $$$L_i = \ell$$$ and $$$R_i = r$$$.
• "?$$$\ a \ b$$$" : this indicates the query, given the interval of guards $$$[a,b]$$$, how many cells are watch over by all the guards in this interval.

Note that, at each moment, each guard has a single interval of cells assigned to him.

Constraints

• $$$1 \leq N, Q \leq 2 \cdot 10^5$$$
• $$$-10^9 \leq L_i \leq R_i \leq 10^9$$$
• For each operation of type 'C', $$$1 \leq i \leq N$$$ and $$$-10^9 \leq \ell \leq r \leq 10^9$$$
• For each operation of type '?', $$$1 \leq a \leq b \leq N$$$
• There is at least one operation of type '?'

For each operation of type '?', print a line with the answer.

3 4
1 100
5 10
7 20
? 1 3
? 2 3
C 1 8 8
? 1 3

4
4
1

2 3
1 2
9 10
? 1 1
? 2 2
? 1 2

2
2
0