{"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\u003eAlex is a professional computer game player.\u003c/p\u003e\u003cp\u003eThese days, Alex is playing an interstellar game. This game is played in an infinite 2D universe, and Alex\u0027s spaceship starts at $$$(0,0)$$$ in the beginning. Because the distances between different galaxies are too long (conventional thrusters cannot reach the destination in an acceptable amount of time), movement can only be done by \"jump\". If his spaceship has jump skill $$$(a,b)$$$ and he is located at $$$(x,y)$$$, he can reach $$$(x+a,y+b)$$$ or $$$(x-a,y-b)$$$ immediately. He can use jump skills continuously at any time, and the jump skills will not disappear.\u003c/p\u003e\u003cp\u003eIn the game, the following $$$Q$$$ events, which have two types, will happen in order.\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$1\\ x_i\\ y_i$$$: Alex will acquire jump skill $$$(x_i,y_i)$$$. \u003c/li\u003e\u003cli\u003e $$$2\\ x_i\\ y_i\\ w_i$$$: There will be a reward mission in $$$(x_i,y_i)$$$. Alex can decide to go there immediately for $$$w_i$$$ rewards or just ignore it. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eAlex wonders how many rewards he can get if he plays optimally.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input gives the number of test cases, $$$T\\ (1 \\le T \\le 10^4)$$$. $$$T$$$ test cases follow.\u003c/p\u003e\u003cp\u003eFor each test case, the first line contains a integer $$$Q\\ (1 \\le Q \\le 10^5)$$$, where $$$Q$$$ is the number of the following events.\u003c/p\u003e\u003cp\u003eEach of the following $$$Q$$$ lines contains three or four integers $$$t_i\\ (1\\le t_i \\le 2)$$$, $$$x_i,y_i\\ (0 \\le x_i,y_i \\le 10^6)$$$ and maybe $$$w_i\\ (1 \\le w_i \\le 10^9)$$$, describing the following events.\u003c/p\u003e\u003cp\u003eThe sum of $$$Q$$$ in all test cases doesn\u0027t exceed $$$10^6$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output one line containing \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eCase #x: y\u003c/span\u003e\", where $$$\\texttt{x}$$$ is the test case number (starting from $$$1$$$), and $$$\\texttt{y}$$$ is the maximum rewards Alex can get.\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\n4\n1 1 1\n2 3 1 1\n1 1 3\n2 3 1 2\n3\n1 1 1\n1 2 1\n2 3 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 2\nCase #2: 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}