{"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\u003eYou are given a rooted tree. Each vertex contains $$$a_i$$$ tons of gold, which costs $$$c_i$$$ per one ton. Initially, the tree consists only a root numbered $$$0$$$ with $$$a_0$$$ tons of gold and price $$$c_0$$$ per ton.\u003c/p\u003e\u003cp\u003eThere are $$$q$$$ queries. Each query has one of two types: \u003c/p\u003e\u003col\u003e \u003cli\u003e Add vertex $$$i$$$ (where $$$i$$$ is an index of query) as a son to some vertex $$$p_i$$$; vertex $$$i$$$ will have $$$a_i$$$ tons of gold with $$$c_i$$$ per ton. It\u0027s guaranteed that $$$c_i \u0026gt; c_{p_i}$$$. \u003c/li\u003e\u003cli\u003e For a given vertex $$$v_i$$$ consider the simple path from $$$v_i$$$ to the root. We need to purchase $$$w_i$$$ tons of gold from vertices on this path, spending the minimum amount of money. If there isn\u0027t enough gold on the path, \u003cspan class\u003d\"tex-font-style-bf\"\u003ewe buy all we can\u003c/span\u003e. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eIf we buy $$$x$$$ tons of gold in some vertex $$$v$$$ the remaining amount of gold in it decreases by $$$x$$$ (of course, we can\u0027t buy more gold that vertex has at the moment). For each query of the second type, calculate the resulting amount of gold we bought and the amount of money we should spend.\u003c/p\u003e\u003cp\u003eNote that you should solve the problem in \u003cspan class\u003d\"tex-font-style-tt\"\u003eonline\u003c/span\u003e mode. It means that you can\u0027t read the whole input at once. You can read each query only after writing the answer for the last query, so don\u0027t forget to flush output after printing answers. You can use functions like \u003cspan class\u003d\"tex-font-style-tt\"\u003efflush(stdout)\u003c/span\u003e in \u003cspan class\u003d\"tex-font-style-tt\"\u003eC++\u003c/span\u003e and \u003cspan class\u003d\"tex-font-style-tt\"\u003eBufferedWriter.flush\u003c/span\u003e in \u003cspan class\u003d\"tex-font-style-tt\"\u003eJava\u003c/span\u003e or similar after each writing in your program. In standard (if you don\u0027t tweak I/O), \u003cspan class\u003d\"tex-font-style-tt\"\u003eendl\u003c/span\u003e flushes \u003cspan class\u003d\"tex-font-style-tt\"\u003ecout\u003c/span\u003e in \u003cspan class\u003d\"tex-font-style-tt\"\u003eC++\u003c/span\u003e and \u003cspan class\u003d\"tex-font-style-tt\"\u003eSystem.out.println\u003c/span\u003e in \u003cspan class\u003d\"tex-font-style-tt\"\u003eJava\u003c/span\u003e (or \u003cspan class\u003d\"tex-font-style-tt\"\u003eprintln\u003c/span\u003e in \u003cspan class\u003d\"tex-font-style-tt\"\u003eKotlin\u003c/span\u003e) makes automatic flush as well. \u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains three integers $$$q$$$, $$$a_0$$$ and $$$c_0$$$ ($$$1 \\le q \\le 3 \\cdot 10^5$$$; $$$1 \\le a_0, c_0 \u0026lt; 10^6$$$)\u0026nbsp;— the number of queries, the amount of gold in the root and its price.\u003c/p\u003e\u003cp\u003eNext $$$q$$$ lines contain descriptions of queries; The $$$i$$$-th query has one of two types: \u003c/p\u003e\u003cul\u003e \u003cli\u003e \"$$$1$$$ $$$p_i$$$ $$$a_i$$$ $$$c_i$$$\" ($$$0 \\le p_i \u0026lt; i$$$; $$$1 \\le a_i, c_i \u0026lt; 10^6$$$): add vertex $$$i$$$ as a son to vertex $$$p_i$$$. The vertex $$$i$$$ will have $$$a_i$$$ tons of gold with price $$$c_i$$$ per one ton. It\u0027s guaranteed that $$$p_i$$$ exists and $$$c_i \u0026gt; c_{p_i}$$$.\u003c/li\u003e\u003cli\u003e \"$$$2$$$ $$$v_i$$$ $$$w_i$$$\" ($$$0 \\le v_i \u0026lt; i$$$; $$$1 \\le w_i \u0026lt; 10^6$$$): buy $$$w_i$$$ tons of gold from vertices on path from $$$v_i$$$ to $$$0$$$ spending the minimum amount of money. If there isn\u0027t enough gold, we buy as much as we can. It\u0027s guaranteed that vertex $$$v_i$$$ exist. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eIt\u0027s guaranteed that there is at least one query of the second type.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each query of the second type, print the resulting amount of gold we bought and the minimum amount of money we should spend.\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\u003e5 5 2\n2 0 2\n1 0 3 4\n2 2 4\n1 0 1 3\n2 4 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2 4\n4 10\n1 3\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":"\u003cp\u003eExplanation of the sample:\u003c/p\u003e\u003cp\u003eAt the first query, the tree consist of root, so we purchase $$$2$$$ tons of gold and pay $$$2 \\cdot 2 \u003d 4$$$. $$$3$$$ tons remain in the root.\u003c/p\u003e\u003cp\u003eAt the second query, we add vertex $$$2$$$ as a son of vertex $$$0$$$. Vertex $$$2$$$ now has $$$3$$$ tons of gold with price $$$4$$$ per one ton.\u003c/p\u003e\u003cp\u003eAt the third query, a path from $$$2$$$ to $$$0$$$ consists of only vertices $$$0$$$ and $$$2$$$ and since $$$c_0 \u0026lt; c_2$$$ we buy $$$3$$$ remaining tons of gold in vertex $$$0$$$ and $$$1$$$ ton in vertex $$$2$$$. So we bought $$$3 + 1 \u003d 4$$$ tons and paid $$$3 \\cdot 2 + 1 \\cdot 4 \u003d 10$$$. Now, in vertex $$$0$$$ no gold left and $$$2$$$ tons of gold remain in vertex $$$2$$$.\u003c/p\u003e\u003cp\u003eAt the fourth query, we add vertex $$$4$$$ as a son of vertex $$$0$$$. Vertex $$$4$$$ now has $$$1$$$ ton of gold with price $$$3$$$.\u003c/p\u003e\u003cp\u003eAt the fifth query, a path from $$$4$$$ to $$$0$$$ consists of only vertices $$$0$$$ and $$$4$$$. But since no gold left in vertex $$$0$$$ and only $$$1$$$ ton is in vertex $$$4$$$, we buy $$$1$$$ ton of gold in vertex $$$4$$$ and spend $$$1 \\cdot 3 \u003d 3$$$. Now, in vertex $$$4$$$ no gold left.\u003c/p\u003e"}}]}