{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe 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$$$\u003c/p\u003e\u003cp\u003eEach 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: \u003c/p\u003e\u003col\u003e \u003cli\u003e Given a guard $$$i$$$, change the interval of cells assigned to him to $$$[\\ell,r]$$$; \u003c/li\u003e\u003cli\u003e Given an interval of guards $$$[a,b]$$$, find how many cells are watched by all the guards in this interval at the moment. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eYour 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.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe 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\u003c/p\u003e\u003cul\u003e \u003cli\u003e \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eC\u003c/span\u003e$$$\\ i \\ \\ell \\ r$$$\": this indicates changing the interval of cells of the $$$i$$$th guard to $$$L_i \u003d \\ell$$$ and $$$R_i \u003d r$$$. \u003c/li\u003e\u003cli\u003e \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e?\u003c/span\u003e$$$\\ 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. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eNote that, at each moment, each guard has a single interval of cells assigned to him.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eConstraints\u003c/span\u003e \u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$1 \\leq N, Q \\leq 2 \\cdot 10^5$$$ \u003c/li\u003e\u003cli\u003e $$$-10^9 \\leq L_i \\leq R_i \\leq 10^9$$$ \u003c/li\u003e\u003cli\u003e For each operation of type \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eC\u003c/span\u003e\u0027, $$$1 \\leq i \\leq N$$$ and $$$-10^9 \\leq \\ell \\leq r \\leq 10^9$$$ \u003c/li\u003e\u003cli\u003e For each operation of type \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e?\u003c/span\u003e\u0027, $$$1 \\leq a \\leq b \\leq N$$$ \u003c/li\u003e\u003cli\u003e There is at least one operation of type \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e?\u003c/span\u003e\u0027 \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each operation of type \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003e?\u003c/span\u003e\u0027, print a line with the answer.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 4\n1 100\n5 10\n7 20\n? 1 3\n? 2 3\nC 1 8 8\n? 1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n4\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 3\n1 2\n9 10\n? 1 1\n? 2 2\n? 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n2\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}