Problem Statement

A psychic, Takahashi, has discovered a treasure map. According to the map, there are 50 buried treasures under the ground of an uninhabited island. The island has a circular shape with a radius of R=10^9. Unfortunately, the map does not indicate the locations of the buried treasures. Since it is impossible to dig up all the ground, he decided to use his psychic powers to search for the treasures in the following way.

1. Choose a desired location and stand a wooden rod.
2. If there is a treasure within a radius of D=10^6 from the chosen location, the rod will remain standing, and he can find the treasure by digging all the area within the radius D.
3. If there are no treasures within a radius of D from the chosen location, the rod will fall in a certain direction according to the rule described below, providing a clue to the location of the treasures.

By repeating this process up to 1000 times, find as many treasures as possible, as quickly as possible.

The law of the falling direction of the rod

Let q=(qx, qy) be the coordinates at which the rod stands, then the falling direction \theta (0\leq \theta<2\pi) is calculated as follows, using a constant \sigma given as an input.

1. Among the treasures that have not yet been dug up, one is chosen with probability proportional to the inverse of the squared Euclidean distance to q.
2. Let p=(px,py) be the coordinates of the chosen treasure, and calculate the direction \hat{\theta}=\mathrm{atan2}(py-qy,px-qx) of p-q.
3. Sample a value from Gaussian distribution with mean \hat{\theta} and standard deviation \sigma and let \theta be its remainder divided by 2\pi.

Input and Output

First, the standard deviation \sigma is given in a single line from Standard Input. \sigma is a multiple of 0.001 and satisfies 0.001\leq \sigma\leq 0.100.

After reading the input, repeat the following process up to 1000 times. In the k-th process, first choose the location (qx_k, qy_k) to stand the rod, and output a single line to Standard Output in the following format.

qx_k qy_k

qx_k and qy_k must be integers satisfying qx_k^2+qy_k^2\leq R^2. If you specify a point outside the range, you will get WA. The output must be followed by a new line, and you have to flush Standard Output. Otherwise, the submission might be judged as TLE.

Then, the information about what happened to the rod is given in a single line from Standard Input as follows.

If the rod falls in the direction of \theta_k:

0 \theta_k

\theta_k is between 0 and 2\pi and is given rounded to 10 decimal places.

If the rod remains standing and you find a treasure at the coordinates (x_k,y_k):

r_k x_k y_k

r_k is 2 if the found treasure is the last one, and 1 otherwise. The distance between different treasures is guaranteed to be greater than 2D, so you will not find more than one treasure simultaneously. When you have found all the treasures, you must immediately terminate the program. Otherwise, any subsequent queries will not return a response so the submission might be judged as TLE or RE.

Example

0.051

-449800796 341903569

0 4.2119508044

-302629026 250885846

0 4.7012310463

-132900000 -988000000

1 -132899921 -988157302

Scoring

If you failed to find all the treasures within 1000 queries, the score for the test case is 100F, where F is the number of treasures you found. If you found all the treasures in Q(\leq 1000) queries, the score for the test case is 10000-5Q. If you have not found all the treasures and the number of queries is less than 1000, the submission will be judged as WA.

There are 200 test cases, and the score of a submission is the total score for each test case. If you get a result other than AC for one or more test cases, the score of the submission will be zero. The highest score obtained during the contest time will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, the ranking will be determined by the submission time of the submission that received that score.

Input Generation

Let \mathrm{rand}(L,U) be a function that generates a uniform random integer between L and U, inclusive. \sigma is generated by 0.001\times \mathrm{rand}(1,100). The coordinates p_0\cdots,p_{49} of 50 buried treasures are generated as follows.

1. Generate the coordinates p_i=(px_i,py_i) of the i-th buried treasure uniformly at random among integers satisfying px_i^2+py_i^2\leq R^2.
2. While there is an already generated p_j (j<i) whose Euclidean distance from p_i is less than or equal to 2D, re-generate p_i.

Tools (Input generator, visualizer, and local tester)

• Web version: You can see animations and play manually.
• Local version: 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 during the contest is prohibited.

Specification of input/output files used by the tools

Input files given to the local tester have the following format.

\sigma
px_0 py_0
\vdots
px_{49} py_{49}
\mathrm{seed}

The last \mathrm{seed} is a random seed value used to generate the fallen directions. Since directions depend on the rod's locations, the input file contains only the random seed value.

The local tester writes outputs from your program directly to the output file. Your program may output comment lines starting with #. The visualizer displays the comment lines with the corresponding query, which may be useful for debugging and analysis. Since the judge program ignores all comment lines, you can submit a program that outputs comment lines as is.

Comment lines that begin with the following have special meaning in the visualizer.

• #r: When you do not use the provided local tester, by outputting a response string given to the solution program in the form of #r 0 0.0123456789, you can provide the information to the visualizer. The provided local tester also automatically inserts these comment lines.
• #c: By outputting in the following format, you can mark a point (x, y) with RGB color (r,g,b) (0\leq r,g,b\leq 255). You can utilize this function, for example, to check the possible location of a buried treasure. The marking is removed at each turn, so if necessary, output it every turn.

#c x y r g b