{"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":"\u003cstyle type\u003d\u0027text/css\u0027\u003e .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 \u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027]]}\n });\n \u003c/script\u003e\n \u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n \u003c/script\u003e\n\u003cp\u003eJamal likes trees very much. The various properties of tree amazes him. Recently while walking through the market, he discovered an interesting tree on sale. It was called special 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\n\u003cp\u003eThis 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\n\u003cp\u003eThis tree supports two types of queries:\u003c/p\u003e\n\u003cul\u003e \n \u003cli\u003e \"\u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eval\u003c/i\u003e\u003c/span\u003e\" — \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\n \u003cli\u003e \"\u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e\" — print the current value of node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e. \u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eJamal bought the tree without any hesitation. Now, in order to help Jamal 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\u003eThe 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 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 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 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 1000)\u003c/span\u003e. Each of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e–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 ≤ \u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eu\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \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\n\u003cp\u003eEach 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 ≤ \u003ci\u003ex\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e, 1 ≤ \u003ci\u003eval\u003c/i\u003e ≤ 1000\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor 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":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e5 5\u003cbr\u003e1 2 1 1 2\u003cbr\u003e1 2\u003cbr\u003e1 3\u003cbr\u003e2 4\u003cbr\u003e2 5\u003cbr\u003e1 2 3\u003cbr\u003e1 1 2\u003cbr\u003e2 1\u003cbr\u003e2 2\u003cbr\u003e2 4\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e3\u003cbr\u003e3\u003cbr\u003e0\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eThe values of the nodes are \u003cspan class\u003d\"tex-span\"\u003e[1, 2, 1, 1, 2]\u003c/span\u003e at the beginning.\u003c/p\u003e\n\u003cp\u003eThen value \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e is added to node \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e. It propagates and value -\u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e is added to it\u0027s sons, node \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e and node \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e. Then it cannot propagate any more. So the values of the nodes are \u003cspan class\u003d\"tex-span\"\u003e[1, 5, 1, - 2, - 1]\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003eThen value \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e is added to node \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e. It propagates and value -\u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e is added to it\u0027s sons, node \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e and node \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e. From node \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e it propagates again, adding value \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e to it\u0027s sons, node \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e and node \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e. Node \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e has no sons, so it cannot propagate from there. The values of the nodes are \u003cspan class\u003d\"tex-span\"\u003e[3, 3, - 1, 0, 1]\u003c/span\u003e.\u003c/p\u003e"}}]}