Description

There is a rectangular cake made of blueberries, strawberries, and chocolate. Its shape is like a square: the bottom-left corner is at $(-5000,-5000)$ and the top-right corner is at $(5000,5000)$ (the unit of the coordinate system is millimeters). Its area is $100$ square meters.

Professionals strongly recommend eating this cake with a wet knife and a dry spoon. Also:

• The starting point of each cut is on the boundary of the cake.
• A single cut cannot lie entirely on the boundary of the cake.
• No two cuts have the same start point and end point; that is, all cutting segments are different.

You may separate and count the pieces only after the last cut is made. In other words, during the cutting process, the cake always remains a rectangle.

Find the minimum number of cuts needed to cut the cake into at least $k$ pieces, and output the coordinates of the start and end points of each cut.

Input Format

One line with one integer $k$, meaning the cake must be cut into at least $k$ pieces.

Output Format

The first line contains one integer $n$, the minimum number of cuts.

The next $n$ lines each contain four integers: the coordinates of the start point and the end point of this cut.

For every point on the boundary of the cake, it is guaranteed that $\max(|x|,|y|)=5000$.

1

0

4

2
-5000 -5000 5000 5000
5000 -5000 -5000 5000

7

3
-5000 5000 0 -5000
-2000 -5000 5000 5000
-5000 0 5000 0

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1\le k\le 10^6$.

Notes

This problem is translated from COCI2011-2012 CONTEST #6 T4 REZ.

Translated by ChatGPT 5