담배 재배

도시에 꽃이 만발한 아름다운 공원이 있다. 이 공원은 시민들에게 인기가 많고 특히 아이를 동반한 가족들이 자주 찾는다. 갱단은 이 지역으로 범죄 활동을 확장하려 하며, 주된 목표는 담배 생산이다. 갱단은 공원에 담배 씨앗을 몰래 심어 경찰의 눈을 피해 키우기로 했다. 때가 되면 한 번의 작업으로 최대한 많은 담배를 수확해 국경을 넘어 밀수할 계획이다.

공원은 각 방향으로 좌표가 −106에서 106까지인 꽃 타일들로 이루어져 있다. 좌표 (X, Y)의 타일은 좌표 (X + 1, Y), (X − 1, Y), (X, Y + 1), (X, Y − 1)의 타일과 이웃한다(좌표 범위 안에서). 첫날에 갱단은 원하는 타일의 꽃을 자를 수 있다. 또한 첫날에만, 타일의 꽃을 잘랐다면 그 타일에 담배를 심거나 풀만 남겨 둘 수 있다. 처음에 담배가 있는 타일의 담배 양은 1이고, 풀이 있는 타일이나 꽃이 있는 타일의 담배 양은 0이다. 담배는 상당히 빠르게 퍼지므로, 이후 매일 공원 타일의 담배 양은 다음과 같이 증가한다:

• 담배와 풀이 있는 타일의 담배 양은 전날 이웃 타일의 담배 양의 합만큼 증가한다.
• 꽃이 있는 타일의 담배 양은 항상 0으로 유지된다.

며칠 동안 담배를 키운 뒤 특정한 날에 수확 작업이 이루어진다. 갱단은 (종류에 상관없이) 일부 타일을 골라 수확해 그날 그 타일들의 담배 양을 모두 얻는다. 각 타일은 최대 한 번만 수확할 수 있고, 고른 타일의 담배 양은 전부 수확해야 한다. 밀수할 수 있는 담배 양에는 한계가 있어 갱단은 전부를 수확할 수 없다. 동시에 불필요한 손해를 보고 싶지 않으므로 한계량만큼 정확히 수확하려 한다.

갱단이 작업을 세세하게 계획하도록 돕는 것이 과제이다. 구체적으로는 다음과 같다:

1. 첫날에 자를 꽃 타일을 고르고, 그중 담배를 심을 타일을 고른다. 경찰의 의심을 사지 않도록 꽃 타일은 최대 2 · 105개까지 자를 수 있다.
2. 담배를 키울 일수를 정한다. 이 담배 사업이 뻔히 드러나지 않도록 일수는 최대 100이어야 한다.
3. 주어진 일수가 지난 뒤 수확할 타일을 고른다. 수확할 타일은 최대 104개까지 가능하다. 그보다 많으면 갱단의 시간이 너무 오래 걸린다.

갱단을 도울 수 있겠는가? 행운을 빈다!

입력은 정확히 수확할 담배 양인 정수 N (0 ≤ N ≤ 1018) 하나를 담은 한 줄로 이루어진다.

첫 줄에 자른 꽃 타일의 수 C (0 ≤ C ≤ 2 · 105)를 출력한다. 그러한 타일마다 한 줄씩, 정수 좌표 (X, Y)의 잘린 타일에 담배를 심은 경우 X Y 1, 잘린 타일을 풀밭으로 남긴 경우 X Y 0 형식으로 출력한다(−106 ≤ X, Y ≤ 106).

그다음 수확할 타일의 수 H와 담배를 키울 일수 D (0 ≤ H ≤ 104, 0 ≤ D ≤ 100)를 공백으로 구분해 한 줄에 출력한다. 이어서 H개의 줄에 D일 뒤 수확할 타일의 좌표 X와 Y (−106 ≤ X, Y ≤ 106)를 공백으로 구분해 출력한다.

그림 1: 예제 입력 2의 그림