There is a square on the plane. The coordinates of its lower left corner, upper left corner, lower right corner and upper right corner are $$$(0,0)$$$, $$$(0,10^9)$$$, $$$(10^9,0)$$$ and $$$(10^9,10^9)$$$ respectively.
Given a positive integer $$$k$$$, you need to partition this square into exactly $$$k$$$ acute triangles. That is, find $$$k$$$ acute triangles where any two triangles do not overlap (however they can share a point or a segment) and the union of all triangles equals the square.
There is only one test case in each test file.
The first only line contains a single integer $$$k$$$ ($$$1 \leq k \leq 50$$$).
If there doesn't exist a valid partition, output "No" (without quotes).
Otherwise, first output "Yes" (without quotes) in one line. Each of the following $$$k$$$ lines contains six numbers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$, $$$x_3$$$ and $$$y_3$$$ separated by a space, which means that the three points $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$ and $$$(x_3, y_3)$$$ form an acute triangle. Note that the $$$k$$$ acute triangles must be a partition of the square.
To avoid issues related to precisions, we additionally require that the coordinates of the vertices of all triangles must be integers. It can be proven that for all possible inputs of this problem, if the square can be partitioned into $$$k$$$ acute triangles, there always exists a partition satisfying all the constraints.
2
No
24
Yes 0 0 500000000 0 400000000 300000000 1000000000 0 500000000 0 600000000 300000000 0 0 0 500000000 300000000 400000000 0 1000000000 0 500000000 300000000 600000000 0 1000000000 500000000 1000000000 400000000 700000000 1000000000 1000000000 500000000 1000000000 600000000 700000000 1000000000 1000000000 1000000000 500000000 700000000 600000000 1000000000 0 1000000000 500000000 700000000 400000000 0 0 400000000 300000000 300000000 400000000 0 500000000 300000000 400000000 300000000 600000000 0 1000000000 300000000 600000000 400000000 700000000 500000000 1000000000 400000000 700000000 600000000 700000000 1000000000 1000000000 600000000 700000000 700000000 600000000 1000000000 500000000 700000000 600000000 700000000 400000000 1000000000 0 700000000 400000000 600000000 300000000 500000000 0 400000000 300000000 600000000 300000000 500000000 500000000 400000000 300000000 300000000 400000000 500000000 500000000 300000000 400000000 300000000 600000000 500000000 500000000 300000000 600000000 400000000 700000000 500000000 500000000 400000000 700000000 600000000 700000000 500000000 500000000 600000000 700000000 700000000 600000000 500000000 500000000 700000000 600000000 700000000 400000000 500000000 500000000 700000000 400000000 600000000 300000000 500000000 500000000 600000000 300000000 400000000 300000000
The following figure shows the division given by the second sample case.
