{"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\u003eBarney lives in NYC. NYC has infinite number of intersections numbered with positive integers starting from 1. There exists a bidirectional road between intersections \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e2\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e and another road between \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e2\u003ci\u003ei\u003c/i\u003e + 1\u003c/span\u003e for every positive integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e. You can clearly see that there exists a unique shortest path between any two intersections.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/dab08b3a5ece2c2ba821cd0e6b0dc1b9?v\u003d1714758313\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eInitially anyone can pass any road for free. But since SlapsGiving is ahead of us, there will \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e consecutive events happen soon. There are two types of events:\u003c/p\u003e\u003cp\u003e1. Government makes a new rule. A rule can be denoted by integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e. As the result of this action, the passing fee of all roads on the shortest path from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e increases by \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e dollars. \u003c/p\u003e\u003cp\u003e2. Barney starts moving from some intersection \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e and goes to intersection \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e where there\u0027s a girl he wants to cuddle (using his fake name Lorenzo Von Matterhorn). He always uses the shortest path (visiting minimum number of intersections or roads) between two intersections.\u003c/p\u003e\u003cp\u003eGovernment needs your calculations. For each time Barney goes to cuddle a girl, you need to tell the government how much money he should pay (sum of passing fee of all roads he passes).\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input contains a single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eq\u003c/i\u003e ≤ 1 000\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eThe next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e lines contain the information about the events in chronological order. Each event is described in form \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e if it\u0027s an event when government makes a new rule about increasing the passing fee of all roads on the shortest path from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e by \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003c/span\u003e dollars, or in form \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e if it\u0027s an event when Barnie goes to cuddle from the intersection \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e to the intersection \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ev\u003c/i\u003e, \u003ci\u003eu\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e18\u003c/sup\u003e, \u003ci\u003ev\u003c/i\u003e ≠ \u003ci\u003eu\u003c/i\u003e, 1 ≤ \u003ci\u003ew\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e states for every description line.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each event of second type print the sum of passing fee of all roads Barney passes in this event, in one line. Print the answers in chronological order of corresponding events.\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\u003e7\n1 3 4 30\n1 4 1 2\n1 3 6 8\n2 4 3\n1 6 1 40\n2 3 7\n2 2 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e94\n0\n32\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\u003eIn the example testcase:\u003c/p\u003e\u003cp\u003eHere are the intersections used:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/ef3b8eb4e08a38f59f7c6397c3c03fcd?v\u003d1714758313\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003col\u003e \u003cli\u003e Intersections on the path are \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e Intersections on the path are \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e Intersections on the path are only \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e Intersections on the path are \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e. Passing fee of roads on the path are \u003cspan class\u003d\"tex-span\"\u003e32\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e32\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e30\u003c/span\u003e in order. So answer equals to \u003cspan class\u003d\"tex-span\"\u003e32 + 32 + 30 \u003d 94\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e Intersections on the path are \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e Intersections on the path are \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e7\u003c/span\u003e. Passing fee of the road between them is \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e Intersections on the path are \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e. Passing fee of the road between them is \u003cspan class\u003d\"tex-span\"\u003e32\u003c/span\u003e (increased by \u003cspan class\u003d\"tex-span\"\u003e30\u003c/span\u003e in the first event and by \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e in the second). \u003c/li\u003e\u003c/ol\u003e"}}]}