The sun is a deadly laser

hi12bye17은 평범한 집에서 평화로운 삶을 사는 마법사이다. 최근에 중요한 일을 마치고 온 hi12bye17은 $D$일 동안 집에서 평화롭게 휴식을 취하기로 했다. 하지만 매일 아침이 되면 집에 직사광선이 들면서 hi12bye17의 평화로운 잠을 방해하기 때문에 hi12bye17은 마법진을 사용하여 집에 드는 직사광선을 모두 막기로 했다.

hi12bye17이 사는 집은 $N$행 $M$열의 격자판 모양이며, 다양한 크기를 가진 직사각형 모양의 방으로 이루어져 있다. hi12bye17은 집의 $r$행 $c$열을 칸 $(r, c)$라고 부른다.

각 방에는 발동 시 하루 동안 직사광선을 막아주는 마법진이 그려져 있다. 칸 $(r, c)$가 속한 방에 그려진 마법진을 발동하기 위해서는 $A_{r, c}$만큼의 마력을 사용해야 한다. 모든 마법진은 발동할 때마다 마력을 사용해야 한다.

다음은 hi12bye17이 사는 집의 방 구조가 될 수 있는 경우이다.

반면 다음은 hi12bye17이 사는 집의 방 구조가 될 수 없는 경우이다.

hi12bye17은 집에 드는 직사광선을 다음과 같이 막기로 했다.

우선 hi12bye17은 매일 저녁 잠을 자기 전에 미래 예지 마법을 사용하여 내일 아침에는 왼쪽 위 칸이 $(r_1, c_1)$이고 오른쪽 아래 칸이 $(r_2, c_2)$인 직사각형 모양의 구역에 직사광선이 든다는 것을 예견한다.

$D$일 동안 hi12bye17이 직사광선을 막는 데 사용할 마력을 구해보자.

첫째 줄에 hi12bye17이 사는 집의 행의 수 $N$, 열의 수 $M$, hi12bye17이 집에 머무른 일수 $D$가 공백으로 구분되어 주어진다. $(1 \le N, M \le 1\,217;$

hi12bye17이 직사광선을 막는 데 사용할 마력을 $D$개의 줄에 걸쳐 출력한다.