Your task is to design a safe room for a priceless treasure item.
The room will have the shape of a box with dimensions \(a\times b\times c\). You get to choose the dimensions (they have to be positive integers). The smaller the room, the better protected it will be.
Like in all the movies, you have laser sensors to protect the room. More precisely, you have \(2n\) small gadgets: \(n\) emitters and \(n\) receivers. You will have to install all of them inside the safe room according to the specifications below.
Each gadget must be installed at integer coordinates that are within \([0,a-1] \times [0,b-1] \times [0,c-1]\). The gadgets must be placed at \(2n\) mutually distinct of those points.
Once the security system is activated, each emitter will start shining laser beams at all possible receivers, so the room will be criss-crossed by a mesh of \(n^2\) laser beams. And of course, if an intruder breaks any of the beams at any point, the corresponding receiver will trigger an alarm.
The system will operate properly if and only if there is no interference between different laser beams. This means that the emitters and the receivers must be placed so that the \(n^2\) line segments that represent the laser beams are all mutually disjoint.
(Obviously, two line segments that share the same endpoint do not count as intersecting. Formally, we consider open line segments, i.e., line segments without their endpoints.)
Pick the values \(a\), \(b\), and \(c\): the dimensions of your room. Your task is to minimize the volume of that room, i.e., the value \(abc\).
Then, install the \(n = 100\) emitters and \(n = 100\) receivers into the chosen room in a valid way.
There is no input.
The first line of your output file should contain three positive integers \(a,b,c\leq 1\,000\).
Each of the next \(n\) lines should contain three non-negative integers: the coordinates of one emitter. The first coordinate must be between \(0\) and \(a-1\), inclusive, the second between \(0\) and \(b-1\), inclusive, and the third between \(0\) and \(c-1\), inclusive.
Afterwards, the second block of \(n\) lines should describe the receivers in the same format.
Special rule: Resubmissions for this problem do not generate penalty minutes.
Special rule: This subproblem is classified as neither public nor secret. During the contest, you will be able to see the evaluation results (so you’ll know whether your solution was accepted and also its score) but the public ranklist will not show your score: any submission will appear as “potential 100 points” instead.
Note that the limit on the number of submissions is still in place.
If you submit a valid solution with volume \(v\), we will calculate the following value: \(f(v) = 10 + \left(150\,000\,000 / v^{1.5}\right)\).
This value, rounded to two decimal places and capped at 100, will be your score.
Below is a valid (but nowhere near optimal) output for \(n=5\). In this output we choose a \(5\times 10\times 20\) box as the room.
5 10 20
0 3 10
3 7 16
4 3 4
4 6 1
1 0 3
0 6 8
1 1 3
4 4 5
3 8 3
3 6 12