시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB3041089338.912%

문제

2차원 좌표평면 위에 왼쪽 아래 꼭짓점이 $(0,0)$, 오른쪽 위 꼭짓점이 $(N,M)$인 직사각형이 주어진다. 다음 시행을 여러 번 반복하여 이 직사각형의 일부를 색칠할 수 있다.

  • 좌표평면 위의 두 격자점 $A(x_1, y_1)$, $B(x_2, y_2)$를 골라, $A$를 왼쪽 아래 꼭짓점으로 하고 $B$를 오른쪽 위 꼭짓점으로 하는 직사각형 영역을 색칠한다. ($x_1, y_1, x_2, y_2$는 정수; $0\le x_1<x_2\le N$; $0\le y_1<y_2\le M$)
  • 단, 새로 색칠하려는 직사각형의 내부에 이미 색칠된 영역이 있어서는 안 된다. 직사각형의 경계는 직사각형의 내부로 보지 않는다.

민재는 총 색칠된 넓이가 $X$가 되도록 하고 싶다. $N$, $M$, $X$가 주어질 때, 최소 횟수의 시행으로 직사각형을 색칠해 보자.

입력

첫 번째 줄에 정수 $N$, $M$, $X$가 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 총 색칠된 넓이가 $X$가 되도록 하는 최소 시행 횟수 $K$를 출력한다.

두 번째 줄부터 $K$개 줄에 걸쳐 $A(x_1, y_1)$와 $B(x_2, y_2)$의 좌표를 $x_1, y_1, x_2, y_2$ 순으로 공백으로 구분하여 출력한다.

제한

  • $1\le N,M \le 10^5$
  • $1\le X \le NM$
  • $0\le x_1<x_2\le N$
  • $0\le y_1<y_2\le M$

서브태스크

번호배점제한
117

$X$는 $N$의 배수

223

$N, M \le 1\,000$

360

추가 제약 조건 없음

예제 입력 1

5 5 17

예제 출력 1

2
0 0 4 4
4 4 5 5

예제 입력 2

6 6 5

예제 출력 2

1
1 1 6 2

예제 입력 3

5 4 13

예제 출력 3

2
0 0 3 3
3 0 5 2

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.