Problem Statement

Takahashi wants to operate a flying drone on a two-dimensional plane and visit N destinations in arbitrary order. Let x-axis be east-west and y-axis be north-south. The drone's flight area is a 2\cdot 10^5\times 2\cdot 10^5 square surrounded by four walls with x=-10^5,x=+10^5,y=-10^5,y=+10^5. Furthermore, in addition to these outer walls, there can exist other walls inside.

The drone has a state with position (x,y) and velocity (v_x,v_y). The position and velocity are always integer values. Starting from an initial state of position (s_x,s_y) and velocity (0,0), you can perform either of the following two types of operations each turn.

1. Acceleration: Specify an integer vector (a_x,a_y) to change the velocity of the drone from (v_x,v_y) to (v_x+a_x,v_y+a_y). It must satisfy a_x^2+a_y^2\leq 500^2.
2. Measurement: Specify a non-zero integer vector (b_x,b_y) and measure the distance from the current drone position (x,y) to the nearest wall in the (b_x,b_y) direction with uncertainty. It must satisfy b_x^2+b_y^2\leq 10^{10}. Extend a ray from the point (x, y) in the direction towards (b_x, b_y) (the ray passing through (x+b_x,y+b_y)) and calculate the Euclidean distance d = \sqrt{(x-x')^2 + (y-y')^2} to the point (x', y') where it first intersects a wall. The resulting value is \mathrm{round}(d\times \alpha), where \alpha is a value sampled from a normal distribution with mean 1 and standard deviation \delta, given as an input parameter. Resample \alpha if \alpha \leq 0. If the ray passes through an endpoint of a wall, it is considered to have hit the wall. However, if the ray is parallel to a wall, it does not count as a hit.

After an operation, the wind causes the drone's velocity to change slightly from (v_x, v_y). Based on the input parameter \epsilon, two samples are drawn from a normal distribution with mean 0 and standard deviation \epsilon. After rounding these sampled values, they are denoted as (f_x, f_y). The new velocity of the drone then becomes (v_x + f_x, v_y + f_y).

At the end of each turn, the current position is updated to (x+v_x, y+v_y) based on the velocity (v_x, v_y) at that moment. However, if the line segment connecting (x, y) and (x+v_x, y+v_y) intersects with a wall (including cases where the line segment and the wall are parallel), it is considered a collision with the wall, and the position update is not performed; instead, the velocity is reset to (0, 0). It is guaranteed that the drone is not in contact with any wall in its initial state, and in the event of a collision, the drone returns to its position before the collision, ensuring that the drone does not begin moving while in contact with a wall.

If there is no collision with a wall, it is checked whether any destination has been reached. A destination (p_x, p_y), which has not yet been visited, is considered reached if the distance between the line segment connecting (x, y) and (x+v_x, y+v_y) and the destination point is 1000 or less. This distance is defined as the minimum distance between any point q on segment S and point p.

You can perform up to 5000 turns of operation, and the operation is completed immediately upon visiting all destinations.

Scoring

Starting with an initial score of 0, the score changes each turn as follows.

1. Score is reduced by 2.
2. If the drone hits a wall, the score is additionally reduced by 100. If it hits multiple walls at once, the score is only reduced by 100.
3. If there is a destination reached for the first time, the score increases by 1000 for each one.

The score at the moment with the highest score up until either 5000 turns have elapsed or all destinations have been visited will be the score for the test case.

If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The sum of the highest scores obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.

Input and Output

First, information is given from Standard Input in the following format.

N M \epsilon \delta
s_x s_y
p_{x,0} p_{y,0}
\vdots
p_{x,N-1} p_{y,N-1}
l_{x,0} l_{y,0} r_{x,0} r_{y,0}
\vdots
l_{x,M-1} l_{y,M-1} r_{x,M-1} r_{y,M-1}

• The number of destinations is fixed at N=10 in all problems.
• The number of walls M excluding the perimeter satisfies 0\leq M\leq 10.
• (s_x,s_y) represents the initial position of the drone, satisfying -10^5< s_x,s_y< 10^5. It is guaranteed that it is not on a wall, including the outer perimeter.
• (p_{x,i},p_{y,i}) denotes the coordinates of the i-th destination, satisfying -10^5\leq p_{x,i},p_{y,i}\leq 10^5. The destinations may be in contact with walls. For each destination, the distance to the initial position and/or other destinations is guaranteed to be at least 5000.
• The (l_{x,i},l_{y,i}) and (r_{x,i},r_{y,i}) represent the coordinates of the i-th wall endpoint and satisfy -10^5\leq l_{x,i},l_{y,i},r_{x,i},r_{y,i}\leq 10^5. The wall has a positive length and is guaranteed to have no common part with any wall other than the perimeter. It is also guaranteed to have no more than one point in common with the outer perimeter. From these conditions, it is guaranteed that all points in the flight area are reachable without passing through the walls.

After reading the above information, repeat the following process for a maximum of 5000 turns.

For acceleration, output the acceleration vector (a_x,a_y) to Standard Output in the following format.

A a_x a_y

For measurements, output the direction (b_x,b_y) to be measured to Standard Output in the following format.

S b_x b_y

Only when performing a measurement, an integer value representing the measurement result is given in a single line from Standard Input.

The output must be followed by a new line, and you have to flush Standard Output. Otherwise, the submission might be judged as TLE. Note that the judge program will not respond to queries after all destinations have been visited nor after 5000 queries have been completed, so waiting for a response may result in a TLE.

At the end of the turn, information on the results of the drone's movement is given from Standard Input in the following format.

c h
q_0 \cdots q_{h-1}

The value c indicates whether or not it collided with a wall, with c=1 if it collided with a wall, and c=0 if it did not. No information about which wall it collided with is available. The value h represents the number of destinations visited for the first time this turn, and each q_i in the next line is the ID of the destination visited for the first time (0\leq q_i\leq N-1). If h=0, the line with q_i is skipped instead of a blank line.

Example

2 0 10.0 0.1
43722 -75332
79243 32532
44002 -77034

A 150 -400

0 0

S 0 1

168969
0 1
1

Input Generation

Let \mathrm{rand}(L,U) be a function that generates a uniform random integer between L and U, inclusive.

We describe the common parts of all the problems. Refer to the "Differences by Problem" section below for the parts specific to each problem.

Generation of s

Generate s_x=\mathrm{rand}(-99999,99999) and s_y=\mathrm{rand}(-99999,99999).

Generation of p_{x,i} p_{y,i}

For each i, generate p_{x,i}=\mathrm{rand}(-100000,100000) and p_{y,i}=\mathrm{rand}(-100000,100000). If there is a point in s or (p_{x,j}, p_{y,j}) with Euclidean distance less than 5000, we regenerate (p_{x,i},p_{y,i}).

Generation of walls

For each i, generate walls as follows.

First, generate l_{x,i}=\mathrm{rand}(-90000,90000) and l_{y,i}=\mathrm{rand}(-90000,90000), then set r_{x,i}'=l_{x,i}+\mathrm{rand}(-100000,100000) and r_{y,i}'=l_{y,i}+\mathrm{rand}(-100000,100000). If (l_{x,i},l_{y,i})=(r_{x,i}',r_{y,i}'), we regenerate the i-th wall. If r_{x,i}' is out of range (r_{x,i}'<-100000 or 100000<r_{x,i}') and r_{y,i}' is also out of range, we regenerate the i-th wall. Otherwise, set r_{x,i}=\min(100000,\max(-100000,r_{x,i}')) and r_{y,i}=\min(100000,\max(-100000,r_{y,i}')). If this wall (l_{x,i},l_{y,i})-(r_{x,i},r_{y,i}) has a shared point with another previously generated wall, or if the initial position (s_x,s_y) is on this wall, we regenerate the i-th wall. Otherwise, adopt it as the i-th wall.

Differences by Problem

Tools (Input Generator and Local Tester)

• Local Tester: You need a compilation environment of Rust language.
  • Pre-compiled binary for Windows: If you are not familiar with the Rust language environment, please use this instead.

Please be aware that sharing visualization results or discussing solutions/ideas outside of the team during the contest is prohibited.

Specification of input/output files used by the tools

The input file given to the local tester contains random numbers \alpha and (f_x,f_y) in the following format at the end of the prior information.

\alpha_0
\vdots
\alpha_{4999}
f_{x,0} f_{y,0}
\vdots
f_{x,4999} f_{y,4999}

\alpha_t is the error in the measurement at turn t and (f_{x,t},f_{y,t}) is the change of velocity due to wind at turn t.

Your program may output comment lines starting with #. Since the judge program ignores all comment lines, you can submit a program that outputs comment lines as is. The local tester outputs the following comment line at the beginning of each turn in addition to the output of the solver program.

#p x y
#v v_x v_y

(x,y) and (v_x,v_y) are the coordinates and velocity of the drone at the start of this turn.