Description

This is an output-only problem.

I believe most of you have played the game Gold Miner. If you have not, it is recommended to try it after the contest.

This problem is a bit different from the original game. Please read the rules carefully.

Abstract the mining area as a rectangle of size $2s \times s$. Take the upper-left corner as the origin, the positive $x$-axis to the right, and the positive $y$-axis downward, forming a Cartesian coordinate system.

The miner starts at $(s, 0)$. The miner can move freely along part of the $x$-axis: the line segment from the origin to $(2s, 0)$.

Abstract gold and other items in the mining area as pairwise disjoint circles within this rectangle, each circle having a value, which may be positive or negative.

We abstract a grab as shooting a ray with the miner at one end. If the ray does not intersect any circle (tangency does not count), then the grab is invalid; otherwise, the miner will grab the first circle hit along the ray (i.e., the circle whose nearer intersection point with the ray has the smallest distance to the miner).

The goal of Gold Miner is to grab items with as high a total value as possible within the time limit.

Both moving and grabbing take time. Moving 1 unit of distance costs $k_1$ time. Define the distance of a successful grab as the distance from the miner to the nearer intersection point between the ray and the grabbed circle; each unit of this distance costs $k_2$ time for a valid grab (invalid grabs are ignored for time cost).

You will control the miner by issuing move and grab commands to maximize the total value obtained. If after some operation your total time exceeds the time limit, that operation and all subsequent operations will be ignored. See the Output Format for details.

Because the miner is lazy, he accepts only $2n$ operations ($n$ is the number of circles, regardless of whether grabs are invalid). Extra operations will be ignored.

The judging eps is $10^{-7}$. If the distance between the two intersection points of your ray and a circle does not exceed this eps, it will not be considered an intersection. If the difference between your time used and the time limit does not exceed eps, it will not be considered as exceeding the time limit.

Since this is an output-only problem, we will provide the input data, scoring parameters, and the checker for download. See the link at the end.

Input Format

The first line contains five numbers $s, t, k_1, k_2, n$. The meanings of $s, k_1, k_2$ are as above; $t$ is the time limit; $n$ is the number of circles.

Each of the next $n$ lines contains four numbers $x_i, y_i, r_i, v_i$, representing the $x$-coordinate of the center, the $y$-coordinate of the center, the radius, and the value of the circle with index $i$.

$n$ and $v_i$ are integers; the other quantities may be real numbers.

Output Format

Several lines, each describing one of your operations.

Each line starts with a character m or g, followed by a space. (m: move, g: grab)

If the character is m, it should be followed by a real number $p$ ($0 \leq p \leq 2s$), meaning move the miner to $(p, 0)$.

If the character is g, it should be followed by a real number $a$ ($0.2 \leq a \leq 179.8$), meaning the grab ray makes an angle of $a^\circ$ with the positive $x$-axis.

It is recommended to keep 10 decimal places for these two real numbers.

Operations that exceed the time limit and operations beyond $2n$ will be ignored. If your output file contains illegal information, this test may be judged as 0 points.

4 233 1 1 2
3 3 1 1
5 2 1 -1

m 1
g 45
（仅为一种可能输出）

Hint

Sample Explanation

The miner starts at $(4, 0)$, moves to $(1, 0)$, costing time $3$.

As shown, the miner shoots a ray, grabs the first circle hit, gains value $1$, costing time $2\sqrt{2}$.

Of course, this is not the minimum-time solution; other solutions exist.

Scoring

For each test, if your output does not conform to the output format, you get 0 points.

Otherwise, suppose your total value is $a$. Each test has three scoring parameters: the standard answer $b$, a real number $w$, and an integer $f \in \{0, 1\}$.

If $a < 0$, you get 0 points.

If $a > b$, you get $10 + f$ points (this means you may get 11 points on some tests).

Otherwise, you get $\lfloor 10 (\frac{a}{b})^w \rfloor$ points. (Here $\lfloor x \rfloor$ is the greatest integer not exceeding $x$.)

How to Test and Submit

Download the provided files (see attachments). They include mine1.in ~ mine10.in, mine1.ans ~ mine10.ans, and checker.cpp, checker_win32.exe, tester.bat, testlib.h. The in, ans, and checker.cpp are exactly the same as those actually used on Luogu. For systems other than Windows, you can compile checker.cpp yourself.

For testing, put mine1.out ~ mine10.out in the same directory. For Windows users, run tester.bat, which will automatically invoke checker_win32.exe and return the result for each test. For other systems, manually run checker mine1.in mine1.out mine1.ans to get the result for the first test; similarly for the others.

The checker will return a message like points 0.9 Your ans is aaa, done bbb attempts, time used ccc, ddd remained, meaning you can get 9 points on this test; your obtained value is aaa; you successfully executed the first bbb operations; time used is ccc; and ddd time remains. If the remaining time is negative, it means the last operation (which did not successfully execute) exceeded the time limit.

When submitting, you can directly pack and upload mine1.out ~ mine10.out, or submit outputs for each test one by one.

Translated by ChatGPT 5