#53 직사각형 색칠하기

문제

Statement language

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

좌표평면 위의 두 격자점 $A(x_1,y_1)$ , $B(x_2,y_2)$ 를 골라, 를 왼쪽 아래 꼭짓점으로 하고 를 오른쪽 위 꼭짓점으로 하는 직사각형 영역을 색칠한다. (는 정수; ; )

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

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

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

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

Sample 1

Input

5 5 17

Output

2
0 0 4 4
4 4 5 5

Sample 2

Input

6 6 5

Output

1
1 1 6 2