{"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":"HTML","content":"\u003cp\u003e\r\n\t\u003cspan data-scayt_word\u003d\"Iahub\" data-scaytid\u003d\"1\"\u003eIahub\u003c/span\u003e likes trees very much. Recently he discovered an interesting tree named propagating tree. The tree consists of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e nodes numbered 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, each node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e having an initial value \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. The root of the tree is node \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tThis tree has a special property: when a value \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eval\u003c/i\u003e\u003c/span\u003e is added to a value of node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e, the value -\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eval\u003c/i\u003e\u003c/span\u003e is added to values of all the children of node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e. Note that when you add value -\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eval\u003c/i\u003e\u003c/span\u003e to a child of node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e, you also add -(-\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eval\u003c/i\u003e\u003c/span\u003e) to all children of the child of node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e and so on. Look an example explanation to understand better how it works.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tThis tree supports two types of queries:\u003c/p\u003e\r\n\u003cul\u003e\r\n\t\u003cli\u003e\r\n\t\t\u0026quot;\u003cspan class\u003d\"tex-span\"\u003e1\u0026nbsp;\u003c/span\u003e\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u0026nbsp;\u003c/i\u003e\u003c/span\u003e\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eval\u003c/i\u003e\u003c/span\u003e\u0026quot; \u0026mdash; \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eval\u003c/i\u003e\u003c/span\u003e is added to the value of node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e;\u003c/li\u003e\r\n\t\u003cli\u003e\r\n\t\t\u0026quot;\u003cspan class\u003d\"tex-span\"\u003e2\u0026nbsp;\u003c/span\u003e\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e\u0026quot; \u0026mdash; print the current value of node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003e\r\n\tIn order to help Iahub understand the tree better, you must answer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e queries of the preceding type.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tThe first line contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e\u003cspan class\u003d\"tex-span\"\u003e(1\u0026thinsp;\u0026le;\u0026thinsp;\u003ci\u003en\u003c/i\u003e,\u0026thinsp;\u003ci\u003em\u003c/i\u003e\u0026thinsp;\u0026le;\u0026thinsp;200000)\u003c/span\u003e. The second line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e\u003c/span\u003e, ..., \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e\u003cspan class\u003d\"tex-span\"\u003e(1\u0026thinsp;\u0026le;\u0026thinsp;\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u0026thinsp;\u0026le;\u0026thinsp;1000)\u003c/span\u003e. Each of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u0026ndash;1\u003c/span\u003e lines contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\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\u003eu\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(1\u0026thinsp;\u0026le;\u0026thinsp;\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e,\u0026thinsp;\u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u0026thinsp;\u0026le;\u0026thinsp;\u003ci\u003en\u003c/i\u003e)\u003c/span\u003e, meaning that there is an edge between nodes \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\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\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tEach of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e lines contains a query in the format described above. It is guaranteed that the following constraints hold for all queries: \u003cspan class\u003d\"tex-span\"\u003e1\u0026thinsp;\u0026le;\u0026thinsp;\u003ci\u003ex\u003c/i\u003e\u0026thinsp;\u0026le;\u0026thinsp;\u003ci\u003en\u003c/i\u003e,\u0026thinsp;1\u0026thinsp;\u0026le;\u0026thinsp;\u003ci\u003eval\u003c/i\u003e\u0026thinsp;\u0026le;\u0026thinsp;1000\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tFor each query of type two (print the value of node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e) you must print the answer to the query on a separate line. The queries must be answered in the order given in the input.\u003c/p\u003e"}},{"title":"Example","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e\r\n.input, .output {border: 1px solid #888888;} .output {margin-bottom:1em;position:relative;top:-1px;} .output pre,.input pre {background-color:#EFEFEF;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#FFFFFF;border-bottom: 1px solid #888888;font-family:arial;font-weight:bold;padding:0.25em;}\u003c/style\u003e\r\n\u003cdiv class\u003d\"input\"\u003e\r\n\t\u003cdiv class\u003d\"title\"\u003e\r\n\t\tInput\u003c/div\u003e\r\n\t\u003cpre\u003e\r\n\t5 5\r\n1 2 1 1 2\r\n1 2\r\n1 3\r\n2 4\r\n2 5\r\n1 2 3\r\n1 1 2\r\n2 1\r\n2 2\r\n2 4\r\n\u003c/pre\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"output\"\u003e\r\n\t\u003cdiv class\u003d\"title\"\u003e\r\n\t\tOutput\u003c/div\u003e\r\n\t\u003cpre\u003e\r\n\t3\r\n3\r\n0\r\n\u003c/pre\u003e\r\n\u003c/div\u003e"}}]}