{"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\u003eRecently in school Alina has learned what are the \u003cspan class\u003d\"tex-font-style-it\"\u003epersistent data structures\u003c/span\u003e: they are data structures that always preserves the previous version of itself and access to it when it is modified.\u003c/p\u003e\u003cp\u003eAfter reaching home Alina decided to invent her own persistent data structure. Inventing didn\u0027t take long: there is a bookcase right behind her bed. Alina thinks that the bookcase is a good choice for a persistent data structure. Initially the bookcase is empty, thus there is no book at any position at any shelf.\u003c/p\u003e\u003cp\u003eThe bookcase consists of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e shelves, and each shelf has exactly \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e positions for books at it. Alina enumerates shelves by integers from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and positions at shelves\u0026nbsp;— from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e. Initially the bookcase is empty, thus there is no book at any position at any shelf in it.\u003c/p\u003e\u003cp\u003eAlina wrote down \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e operations, which will be consecutively applied to the bookcase. Each of the operations has one of four types:\u003c/p\u003e\u003cul\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e\u0026nbsp;— Place a book at position \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e at shelf \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e if there is no book at it.\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e\u0026nbsp;— Remove the book from position \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e at shelf \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e if there is a book at it.\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e\u0026nbsp;— Invert book placing at shelf \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e. This means that from every position at shelf \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e which has a book at it, the book should be removed, and at every position at shelf \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e which has not book at it, a book should be placed.\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e\u0026nbsp;— Return the books in the bookcase in a state they were after applying \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e-th operation. In particular, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e \u003d 0\u003c/span\u003e means that the bookcase should be in initial state, thus every book in the bookcase should be removed from its position.\u003c/li\u003e\u003c/ul\u003e\u003cp\u003eAfter applying each of operation Alina is interested in the number of books in the bookcase. Alina got \u0027A\u0027 in the school and had no problem finding this values. Will you do so?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains three integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e3\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eq\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;— the bookcase dimensions and the number of operations respectively.\u003c/p\u003e\u003cp\u003eThe next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e lines describes operations in chronological order\u0026nbsp;— \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th of them describes \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th operation in one of the four formats described in the statement.\u003c/p\u003e\u003cp\u003eIt is guaranteed that shelf indices and position indices are correct, and in each of fourth-type operation the number \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e corresponds to some operation before it or equals to \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each operation, print the number of books in the bookcase after applying it in a separate line. The answers should be printed in chronological order.\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\u003e2 3 3\n1 1 1\n3 2\n4 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n4\n0\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\u003e4 2 6\n3 2\n2 2 2\n3 3\n3 2\n2 2 2\n3 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1\n3\n3\n2\n4\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 2 2\n3 2\n2 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003ccenter\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/97e482869a1fbeed0b265cc4e33f44fe?v\u003d1715613718\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003cp\u003eThis image illustrates the second sample case.\u003c/p\u003e\u003c/center\u003e"}}]}