{"trustable":false,"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":"MD","content":"给定一个空的 ``multiset``,你要支持三种操作:\n* ``1 t x`` 表示在时间戳 $t$ 处加入了一个元素 $x$;\n* ``2 t x`` 表示在时间戳 $t$ 时删掉了一个元素 $x$;\n* ``3 t x`` 表示询问时间戳 $t$ 时刻有多少个元素 $x$。\n\n---\n\n\u003cp\u003eLittle Artem has invented a time machine! He could go anywhere in time, but all his thoughts of course are with computer science. He wants to apply this time machine to a well-known data structure: \u003cspan class\u003d\"tex-font-style-underline\"\u003emultiset\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003eArtem wants to create a basic multiset of integers. He wants these structure to support operations of three types:\u003c/p\u003e\n\u003col\u003e\n \u003cli\u003eAdd integer to the multiset. Note that the difference between set and multiset is that multiset may store several instances of one integer.\u003c/li\u003e\n \u003cli\u003eRemove integer from the multiset. Only one instance of this integer is removed. Artem doesn\u0027t want to handle any exceptions, so he assumes that every time remove operation is called, that integer is presented in the multiset.\u003c/li\u003e\n \u003cli\u003eCount the number of instances of the given integer that are stored in the multiset.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp\u003eBut what about time machine? Artem doesn\u0027t simply apply operations to the multiset one by one, he now travels to different moments of time and apply his operation there. Consider the following example.\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003eFirst Artem adds integer \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e to the multiset at the \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e-st moment of time.\u003c/li\u003e\n \u003cli\u003eThen Artem adds integer \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e to the multiset at the moment \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e.\u003c/li\u003e\n \u003cli\u003eThen Artem asks how many \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e are there in the multiset at moment \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e. The answer is \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e.\u003c/li\u003e\n \u003cli\u003eThen Artem returns back in time and asks how many integers \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e are there in the set at moment \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e. Since \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e was added only at moment \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e, the number of integers \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e at moment \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e equals to \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e.\u003c/li\u003e\n \u003cli\u003eThen Artem goes back in time again and removes \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e from the multiset at moment \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e.\u003c/li\u003e\n \u003cli\u003eFinally Artyom asks at moment \u003cspan class\u003d\"tex-span\"\u003e7\u003c/span\u003e how many integers \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e are there in the set. The result is \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e, since we have removed \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e at the moment \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eNote that Artem dislikes exceptions so much that he assures that after each change he makes all delete operations are applied only to element that is present in the multiset. The answer to the query of the third type is computed at the moment Artem makes the corresponding query and are not affected in any way by future changes he makes.\u003c/p\u003e\n\u003cp\u003eHelp Artem implement time travellers multiset.\u003c/p\u003e"}},{"title":"Input","value":{"format":"MD","content":"\u003cp\u003eThe first line of the input contains a single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 100 000\u003c/span\u003e)\u0026nbsp;— the number of Artem\u0027s queries.\u003c/p\u003e\n\u003cp\u003eThen follow \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines with queries descriptions. Each of them contains three integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 3\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;— type of the query, moment of time Artem travels to in order to execute this query and the value of the query itself, respectively. It\u0027s guaranteed that all moments of time are distinct and that after each operation is applied all operations of the first and second types are consistent.\u003c/p\u003e"}},{"title":"Output","value":{"format":"MD","content":"\u003cp\u003eFor each ask operation output the number of instances of integer being queried at the given moment of time.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"MD","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\u003e6\n1 1 5\n3 5 5\n1 2 5\n3 6 5\n2 3 5\n3 7 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n2\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 2","value":{"format":"MD","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\n1 1 1\n2 2 1\n3 3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}