Minimum Cuts to Partition a Rectangular Cake

A rectangular cake made of blueberries, strawberries, and chocolate is given. The cake has the shape of a square with its bottom‐left corner at \( (-5000, -5000) \) and its top‐right corner at \( (5000, 5000) \) (the unit is in millimeters). Its area is \(100\) square meters. Professional advice suggests using a wet knife and a dry spatula when eating the cake.

You are to make several cuts on the cake under the following conditions:

• The starting point of every cut is on the boundary of the cake.
• Each cut is not allowed to lie completely on the boundary, i.e. it must penetrate the interior.
• No two cuts have the same pair of starting and ending points (i.e. all cut lines are distinct).
• The cake remains a full rectangle during the cutting process and is physically separated only after the final cut, at which point the pieces are delineated along the cut lines.

It is known that when \( n \) cuts (in general position) are made, the maximum number of pieces the cake can be partitioned into is given by the formula:

[ P(n)=\frac{n(n+1)}{2}+1 ]

Your task is to, given a number \( k \), find the minimum number of cuts needed so that the cake can be partitioned into at least \( k \) pieces. Moreover, you must output the coordinates of the starting and ending points for each cut. A constructive method is required. One valid construction is as follows:

Suppose the minimum number of cuts determined is \( n \). Define \( \delta = \frac{10000}{n+1} \). For \( i = 1, 2, \dots, n \) let the \( i^{th} \) cut have its starting point at \( (-5000, 5000-i\,\delta) \) (i.e. on the left edge) and its ending point at \( (-5000+i\,\delta, 5000) \) (i.e. on the top edge). It can be verified that for any two distinct cuts \( i \) and \( j \) with \( i < j \), the starting point of cut \( i \) is above that of cut \( j \) while the ending point of cut \( i \) is to the left of that of cut \( j \). Therefore, every pair of cuts will intersect inside the cake, which ensures the maximum number of pieces \( P(n)=\frac{n(n+1)}{2}+1 \) is achieved.

Input Constraints: You may assume \( 1 \le k \le 10^9 \) (or other reasonable upper bound).

inputFormat

The input consists of a single integer k which represents the minimum number of pieces required after cutting the cake.

outputFormat

First, output the minimal number of cuts n needed to obtain at least k pieces. Then, output n lines, each containing four numbers: x1 y1 x2 y2, representing the starting and ending coordinates (in millimeters) of each cut.

If \( k=1 \), output 0 (i.e. no cut is needed).

sample

1

0