케이크 자르기

한 변의 길이가 10m인 정사각형 케이크가 있다. 케이크는 여러 번 직선으로 자를 수 있으며, 각 절단은 다음 조건을 모두 만족해야 한다.

• 각 절단은 케이크의 둘레 위 한 점에서 시작해 둘레 위 다른 한 점에서 끝난다.
• 절단 전체가 정사각형의 한 변 위에 놓이면 안 된다.
• 시작점과 끝점이 모두 같은 두 절단은 없다.

잘린 조각들은 모든 절단이 끝난 뒤에 한꺼번에 분리해서 센다. 자르는 동안 케이크의 바깥 모양은 원래의 정사각형으로 유지된다.

적어도 K개의 조각을 얻기 위해 필요한 최소 절단 횟수를 구하고, 실제로 만들 절단들을 출력하라.

첫째 줄에 필요한 최소 조각 수를 나타내는 정수 K가 주어진다.

1 <= K <= 1 000 000

첫째 줄에 필요한 최소 절단 횟수 N을 출력한다.

다음 N개의 줄에는 각 절단의 시작점과 끝점을 나타내는 네 정수 x1 y1 x2 y2를 출력한다.

좌표는 밀리미터 단위이며, 케이크의 서로 마주 보는 두 꼭짓점은 (-5000, -5000)과 (5000, 5000)이다. 따라서 정사각형의 변 위에 있는 모든 점 (x, y)는 다음 조건을 만족한다.

max(|x|, |y|) = 5000