E. Saki and Hope
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is an output-only problem.

In order to avoid repeating the tragedy that unfolded in her childhood, Saki invented a device which drastically lowers the probability of the Karma Demon appearing!

The earth can be modeled as a sphere with radius $$$1$$$, and Saki is planning to install $$$100\,000$$$ devices on its surface. The effectiveness of the devices is known to be proportional to the number of pairs of devices with Euclidean distance exactly $$$\sqrt2$$$. Here, the Euclidean distance between two people with coordinate $$$(x_0, y_0, z_0)$$$ and $$$(x_1, y_1, z_1)$$$ is $$$\sqrt{(x_0 - x_1)^2 + (y_0 - y_1)^2 + (z_0 - z_1)^2}$$$.

Write a program to install $$$100\,000$$$ devices on distinct locations, such that there exists at least $$$1\,400\,000$$$ pairs of devices with Euclidean distance exactly $$$\sqrt2$$$.

Output

The output should be in the following format:

$$$N$$$
$$$x_0$$$$$$y_0$$$$$$z_0$$$
$$$x_1$$$$$$y_1$$$$$$z_1$$$
$$$\vdots$$$
$$$x_{N-1}$$$$$$y_{N-1}$$$$$$z_{N-1}$$$
$$$M$$$
$$$i_0$$$$$$j_0$$$
$$$i_1$$$$$$j_1$$$
$$$\vdots$$$
$$$i_{M-1}$$$$$$j_{M-1}$$$

where $$$N$$$ is the number of devices, $$$x_i, y_i, z_i$$$ are the parameters indicating that the $$$i$$$-th device is located at the coordinate $$$\left( \frac{x_i}{\sqrt{x_i^2 + y_i^2 + z_i^2}}, \frac{y_i}{\sqrt{x_i^2 + y_i^2 + z_i^2}}, \frac{z_i}{\sqrt{x_i^2 + y_i^2 + z_i^2}} \right)$$$ for each integer $$$0 \le i \lt N$$$, $$$M$$$ is the required number of pairs of devices with Euclidean distance exactly $$$\sqrt2$$$, and $$$i_k, j_k$$$ are the indices of the devices of the $$$k$$$-th pair for all integer $$$0 \le k \lt M$$$.

The output should satisfy the following constraints:

  • All the numbers in the output are integers.
  • $$$N=100\,000$$$
  • $$$-1\,000\,000\,000 \le x_i, y_i, z_i \le 1\,000\,000\,000$$$ and $$$x_i^2 + y_i^2 + z_i^2 \gt 0$$$ for all integer $$$0 \le i \lt N$$$
  • $$$\left( \frac{x_i}{\sqrt{x_i^2 + y_i^2 + z_i^2}}, \frac{y_i}{\sqrt{x_i^2 + y_i^2 + z_i^2}}, \frac{z_i}{\sqrt{x_i^2 + y_i^2 + z_i^2}} \right) \ne \left( \frac{x_j}{\sqrt{x_j^2 + y_j^2 + z_j^2}}, \frac{y_j}{\sqrt{x_j^2 + y_j^2 + z_j^2}}, \frac{z_j}{\sqrt{x_j^2 + y_j^2 + z_j^2}} \right)$$$ for all integers $$$0 \le i \lt j \lt N$$$
  • $$$M=1\,400\,000$$$
  • $$$0 \le i_k \lt j_k \lt N$$$ and $$$x_{i_k} \cdot x_{j_k} + y_{i_k} \cdot y_{j_k} + z_{i_k} \cdot z_{j_k} = 0$$$ (Note that this is equivalent to the Euclidean distance being $$$\sqrt2$$$) for all integers $$$0 \le k \lt M$$$
  • $$$i_k \ne i_l$$$ or $$$j_k \ne j_l$$$ for all integers $$$0 \le k \lt l \lt M$$$
Example
Input
Output
3
1 0 0
0 1 0
0 0 1
3
0 1
0 2
1 2
Note
Please note that the sample output above does not satisfy $$$N=100\,000$$$ or $$$M=1\,400\,000$$$, thus it will give Wrong Answer verdict upon submission. It is there only to present the output format.