{"raw_statement":[{"iden":"statement","content":"Alex is a professional computer game player.\n\nThese days, Alex is playing an interstellar game. This game is played in an infinite 2D universe, and Alex's 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.\n\nIn the game, the following $Q$ events, which have two types, will happen in order.\n\nAlex wonders how many rewards he can get if he plays optimally.\n\nThe first line of the input gives the number of test cases, $T \" \"(1 <= T <= 10^4)$. $T$ test cases follow.\n\nFor each test case, the first line contains a integer $Q \" \"(1 <= Q <= 10^5)$, where $Q$ is the number of the following events.\n\nEach of the following $Q$ lines contains three or four integers $t_i \" \"(1 <= t_i <= 2)$, $x_i, y_i \" \"(0 <= x_i, y_i <= 10^6)$ and maybe $w_i \" \"(1 <= w_i <= 10^9)$, describing the following events.\n\nThe sum of $Q$ in all test cases doesn't exceed $10^6$.\n\nFor each test case, output one line containing \"_Case #x: y_\", where $texttt(x)$ is the test case number (starting from $1$), and $texttt(y)$ is the maximum rewards Alex can get.\n\n"},{"iden":"input","content":"The first line of the input gives the number of test cases, $T \" \"(1 <= T <= 10^4)$. $T$ test cases follow.For each test case, the first line contains a integer $Q \" \"(1 <= Q <= 10^5)$, where $Q$ is the number of the following events.Each of the following $Q$ lines contains three or four integers $t_i \" \"(1 <= t_i <= 2)$, $x_i, y_i \" \"(0 <= x_i, y_i <= 10^6)$ and maybe $w_i \" \"(1 <= w_i <= 10^9)$, describing the following events.The sum of $Q$ in all test cases doesn't exceed $10^6$."},{"iden":"output","content":"For each test case, output one line containing \"_Case #x: y_\", where $texttt(x)$ is the test case number (starting from $1$), and $texttt(y)$ is the maximum rewards Alex can get."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ Q \\in \\mathbb{Z} $ be the number of events.  \nLet $ E = \\{ (t_i, x_i, y_i, w_i) \\mid i \\in \\{1, \\dots, Q\\} \\} $ be the sequence of events, where:  \n- $ t_i \\in \\{1, 2\\} $: event type.  \n- If $ t_i = 1 $: a reward at position $ (x_i, y_i) $ with value $ w_i $ is revealed.  \n- If $ t_i = 2 $: query for the maximum reward reachable from $ (0, 0) $ using jump skills collected so far.  \n\nLet $ J \\subseteq \\mathbb{Z}^2 $ be the set of jump skills acquired from type-1 events.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 10^4 $  \n2. $ 1 \\le Q \\le 10^5 $ per test case  \n3. $ 0 \\le x_i, y_i \\le 10^6 $  \n4. $ 1 \\le w_i \\le 10^9 $  \n5. $ \\sum Q \\le 10^6 $ across all test cases  \n\n**Objective**  \nFor each test case, process events sequentially.  \n- On type-1 event: add $ (x_i, y_i) $ to $ J $.  \n- On type-2 event: compute the maximum $ w_j $ among all rewards $ (x_j, y_j) $ (from previous type-1 events) such that $ (x_j, y_j) $ is reachable from $ (0, 0) $ using integer linear combinations of vectors in $ J $.  \n\nThat is, for a reward at $ (x, y) $, it is reachable iff there exist integers $ c_k \\in \\mathbb{Z} $ such that:  \n$$\n(x, y) = \\sum_{(a_k, b_k) \\in J} c_k \\cdot (a_k, b_k)\n$$  \nThis is equivalent to $ \\gcd(\\{ a_k, b_k \\mid (a_k, b_k) \\in J \\}) $ dividing $ \\gcd(x, y) $.  \n\n**Output**  \nFor each type-2 event, output the maximum $ w_i $ among all reachable rewards up to that point.","simple_statement":"Alex starts at (0, 0) in a 2D universe. He can use jump skills (a, b) to move to (x±a, y±b).  \n\nThere are Q events in order:  \n- Type 1: Add a new jump skill (x_i, y_i).  \n- Type 2: Collect a reward at (x_i, y_i) with value w_i — but only if Alex can reach that point using any combination of jump skills he has collected so far.  \n\nAlex wants the maximum total reward he can collect by choosing optimally which rewards to take.  \n\nOutput the maximum reward for each test case.","has_page_source":false}