Input

Input is given from Standard Input in the following format:

X Y Z
x_0 y_0
\vdots
x_{X+Y+Z-1} y_{X+Y+Z-1}

• The number of burnable trash items X is fixed at X = 100.
• The number of non-burnable trash items Y is either Y = 0 or Y = 100.
• The number of recyclable trash items Z satisfies 0 \leq Z \leq 100.
• Trash coordinates are given as integer pairs (x_i, y_i), where all values satisfy 1 \leq x_i, y_i \leq 10^6 - 1.
• The correspondence between index i and trash type is as follows:
  • i = 0, \dots, X - 1: burnable trash
  • i = X, \dots, X + Y - 1: non-burnable trash
  • i = X + Y, \dots, X + Y + Z - 1: recyclable trash
• The Euclidean distance between any two trash items is guaranteed to be at least 10^3.
• For each of the following four conditions, there exists at least one burnable trash item (x, y) that satisfies it. This ensures that collecting all burnable trash requires at least T \geq 2 \times 10^5 time.
  • x \leq 4 \times 10^5 and y \leq 4 \times 10^5
  • x \leq 4 \times 10^5 and y \geq 6 \times 10^5
  • x \geq 6 \times 10^5 and y \leq 4 \times 10^5
  • x \geq 6 \times 10^5 and y \geq 6 \times 10^5

Output

Let Takahashi's initial left and right hand positions be (x_{0,0}, y_{0,0}) and (x_{0,1}, y_{0,1}), respectively, and Aoki's initial left and right hand positions be (x_{0,2}, y_{0,2}) and (x_{0,3}, y_{0,3}), respectively.

Let K be the number of operations. In the t-th operation (t = 1, 2, \dots, K), Takahashi's left and right hands move to (x_{t,0}, y_{t,0}) and (x_{t,1}, y_{t,1}), respectively, and Aoki's left and right hands move to (x_{t,2}, y_{t,2}) and (x_{t,3}, y_{t,3}), respectively.

Then, output to Standard Output in the following format.

x_{0,0} y_{0,0} x_{0,1} y_{0,1} x_{0,2} y_{0,2} x_{0,3} y_{0,3}
\vdots
x_{K,0} y_{K,0} x_{K,1} y_{K,1} x_{K,2} y_{K,2} x_{K,3} y_{K,3}

In some inputs, there may be no non-burnable trash, in which case Aoki has no tasks to perform. In such cases, for example, you may output x_{t,2} = y_{t,2} = x_{t,3} = y_{t,3} = 0 to have Aoki wait in a corner.

Input Generation

• \mathrm{rand}(L, U): Generates a random integer uniformly distributed between L and U (inclusive).
• \mathrm{rand\_double}(L, U): Generates a random real number uniformly distributed between L and U.
• \mathrm{normal}(\mu, \sigma): Generates a random real number from a normal distribution with mean \mu and standard deviation \sigma.

The ranges of the number of non-burnable trash items Y and recyclable trash items Z for each problem are as follows:

Trash items are generated for each type—in the order of burnable trash → non-burnable trash → recyclable trash—according to the following procedure:

1. Determine the number of trash items N uniformly at random from the specified range.
2. Determine the number of clusters n using \mathrm{rand}(5,10).
3. For each cluster i = 1, \dots, n, generate the following parameters:
   • Weight: w_i = \mathrm{rand\_double}(0, 1)
   • Center coordinates: cx_i, cy_i = \mathrm{rand}(200000, 800000)
   • Standard deviations: \sigma_{x,i}, \sigma_{y,i} = \mathrm{rand}(30000, 90000)
   • Rotation angle: \theta_i = \mathrm{rand\_double}(0, \pi)
4. Repeat the following process N times to generate N trash positions (x, y):
   • Choose a cluster i at random, with probability proportional to its weight w_i.
   • Generate x' = \mathrm{normal}(\sigma_{x,i})、y' = \mathrm{normal}(\sigma_{y,i}).
   • Compute the coordinates (x, y) as follows: \[ x=\mathrm{round}(cx_i+\cos(\theta_i)\cdot x'-\sin(\theta_i)\cdot y')\\ y=\mathrm{round}(cy_i+\sin(\theta_i)\cdot x'+\cos(\theta_i)\cdot y') \]
   • Accept the coordinate (x, y) if it satisfies 1 \leq x, y \leq 10^6 - 1 and is at least 10^3 away (Euclidean distance) from any previously generated trash item. Otherwise, retry the generation of (x, y).

If the type of trash being generated is burnable trash, ensure that there is at least one item in each of the following four regions:

• x \leq 4 \times 10^5 and y \leq 4 \times 10^5
• x \leq 4 \times 10^5 and y \geq 6 \times 10^5
• x \geq 6 \times 10^5 and y \leq 4 \times 10^5
• x \geq 6 \times 10^5 and y \geq 6 \times 10^5

If this condition is not met, restart the process from the cluster generation step.

Regarding Problem C

For Problem C, each team may create their own inputs and overwrite the default ones by submitting them. Refer to the page for Problem D for instructions on how to submit your inputs.

Each team may submit four inputs. Among the four submitted inputs, one is randomly selected and made public to all teams, while the remaining three are used for judging.

The input publication and the start of judging are scheduled to take place approximately 3 hours and 30 minutes after the contest begins. An announcement will be made to all participants once the system is ready.

For any team that does not submit their own inputs, four inputs will be generated randomly according to the input generation procedure described earlier.

Since each team knows the contents of the inputs they submitted, it is allowed to precompute the corresponding outputs and embed them into the solution program.

Submissions to Problem D may be made as many times as desired. However, for each team, only the last submission made within 180 minutes from the start of the contest that receives AC will be used for judging.

Tools (Input generator and score calculation)

• 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 outside of the team during the contest is prohibited.