407349: GYM102769 I Interstellar Hunter

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Interstellar Huntertime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Alex is a professional computer game player.

These 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.

In the game, the following $$$Q$$$ events, which have two types, will happen in order.

  • $$$1\ x_i\ y_i$$$: Alex will acquire jump skill $$$(x_i,y_i)$$$.
  • $$$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.

Alex wonders how many rewards he can get if he plays optimally.

Input

The first line of the input gives the number of test cases, $$$T\ (1 \le T \le 10^4)$$$. $$$T$$$ test cases follow.

For 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.

Each 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.

The sum of $$$Q$$$ in all test cases doesn't exceed $$$10^6$$$.

Output

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.

ExampleInput
2
4
1 1 1
2 3 1 1
1 1 3
2 3 1 2
3
1 1 1
1 2 1
2 3 2 3
Output
Case #1: 2
Case #2: 3

加入题单

上一题 下一题 算法标签: