바이트시아(Bajtocja)와 비토시아(Bitocja)는 수년간의 무의미한 전쟁 끝에 마침내 평화 조약을 체결했습니다. 양국 수도 사이에는 평화의 상징으로 고속도로가 건설되었습니다. 당신은 바이트시아에서 비토시아로 향하는 고속도로 구간의 관리자로 임명되었습니다.*

현재 고속도로에는 1번부터 $m$번까지 번호가 매겨진 $m$개의 요금소가 있습니다. 첫 번째 요금소는 고속도로 시작점에, 마지막 요금소는 끝점에 위치합니다. 요금소를 통과하는 비용은 하루 중 시간에 따라 다를 수 있습니다. 하루는 1부터 $n$까지 번호가 매겨진 $n$개의 시간대로 나뉩니다. 현재 시간 $i$에 요금소 $j$를 통과하는 비용은 $c_{i,j}$ 바이트탈러입니다. 이 비용 중 일부는 0일 수 있으며(이 경우 통과가 무료), 음수일 수도 있습니다(이 경우 운전자가 요금소를 통과할 때 $-c_{i,j}$ 바이트탈러를 받습니다).

고속도로 전체는 한 시간 안에 통과할 수 있을 만큼 짧습니다. 물론 서두를 필요는 없으며, 주행 중에 원하는 만큼 정차할 수 있습니다. 하지만 고속도로에서 숙박할 수는 없으며, 모든 요금소를 같은 날에 통과해야 합니다.

운전자들은 당연히 가능한 한 적은 비용으로 고속도로를 통과하고 싶어 합니다. $1 \le i \le j \le n$에 대하여 $f(i, j)$를 운전자가 첫 번째 요금소를 시간 $i$에 통과하고 마지막 요금소를 시간 $j$에 통과할 때 고속도로 전체를 통과하는 최소 비용이라고 정의합니다. 모든 $f(i, j)$ 값은 양국 정부 간의 평화 조약에 의해 결정되었으므로, 고속도로 관리자인 당신은 이를 변경할 수 없습니다. 그러나 첫 번째와 마지막 요금소는 반드시 열려 있어야 한다는 조건하에, 각 요금소의 통과 비용을 자유롭게 수정하거나 일부 요금소를 완전히 폐쇄할 수 있습니다. 단, $f(i, j)$ 값은 변하지 않아야 하며, 당신이 설정한 모든 비용은 1 바이트탈러의 정수 배수여야 합니다.

고속도로 유지 비용을 최소화하기 위해 가능한 한 많은 요금소를 폐쇄하고자 합니다. 조약 조건을 계속 만족하면서 열어두어야 하는 최소 요금소 개수를 구하십시오.

요금 징수 체계 재구성 프로젝트는 두 단계로 진행됩니다. 첫 번째 단계인 예비 설계에서는 최적의 요금소 개수만 구하면 됩니다. 그러나 두 번째 단계인 구현 단계에서는 남겨둔 요금소에 대한 전체적인 예시 요금표를 추가로 제시해야 합니다.

입력

입력의 첫 번째 줄에는 세 개의 정수 $n, m, q$ ($2 \le n, m \le 30\,000$; $n \cdot m \le 300\,000$; $q \in \{0, 1\}$)가 주어지며, 각각 하루의 시간대 수, 현재 고속도로의 요금소 수, 프로젝트 단계를 나타내는 비트를 의미합니다. $q = 0$은 프로젝트의 첫 번째 단계(예비 설계)를 의미하며, $q = 1$은 프로젝트가 이미 구현 단계에 있음을 의미합니다.

이어지는 $n$개의 줄에는 현재 요금에 대한 설명이 포함되어 있습니다. $i$번째 줄에는 $m$개의 정수 $c_{i,1}, c_{i,2}, \dots, c_{i,m}$ ($-10^6 \le c_{i,j} \le 10^6$)이 주어집니다. $c_{i,j}$ 값은 시간 $i$에 요금소 $j$를 통과하는 비용(바이트탈러)을 나타냅니다. $c_{i,j}$가 음수이면, 시간 $i$에 $j$번째 요금소를 통과할 때 운전자는 $-c_{i,j}$ 바이트탈러를 받습니다.

출력

첫 번째 줄에는 조약의 어떤 $f(i, j)$ 값도 변하지 않도록 고속도로에 남겨두어야 하는 최소 요금소 개수 $k$ ($2 \le k \le m$)를 출력합니다. $q = 0$인 경우, 출력은 이 숫자 하나만 포함하는 한 줄로 구성되어야 합니다.

$q = 1$인 경우, 이어지는 $n$개의 줄에 문제의 조건을 만족하는 예시 최적 요금표를 출력해야 합니다. $i$번째 줄에는 $k$개의 정수 $d_{i,1}, d_{i,2}, \dots, d_{i,k}$ ($-10^{12} \le d_{i,j} \le 10^{12}$)가 포함되어야 합니다. $d_{i,j}$ 값은 시간 $i$에 남겨진 요금소 중 $j$번째 요금소를 통과하는 새로운 비용을 나타냅니다.

문제의 제약 조건 하에서 절대값이 $10^{12}$를 넘지 않는 정수 비용을 항상 결정할 수 있음이 증명되어 있습니다.

예제

예제 입력 1

3 6 1
-1 0 4 0 -3 0
-4 1 5 2 -5 2
-5 2 3 0 -2 2

예제 출력 1

3
0 0 0
0 1 0
0 0 0

참고 1

첫 번째 예제 테스트에서 고속도로를 통과하는 각 최소 비용은 다음과 같습니다: $f(1, 1) = (-1) + 0 + 4 + 0 + (-3) + 0 = 0$, $f(1, 2) = (-1) + 0 + 4 + 0 + (-5) + 2 = 0$, $f(1, 3) = (-1) + 0 + 4 + 0 + (-5) + 2 = 0$, $f(2, 2) = (-4) + 1 + 5 + 2 + (-5) + 2 = 1$, $f(2, 3) = (-4) + 1 + 3 + 0 + (-2) + 2 = 0$, $f(3, 3) = (-5) + 2 + 3 + 0 + (-2) + 2 = 0$.

두 개의 요금소만 사용하여 동일한 통과 비용을 구현하는 것은 불가능합니다. 제안된 비용 $d_{i,j}$에서 요금이 부과되지 않더라도 첫 번째와 마지막 요금소는 폐쇄할 수 없다는 점에 유의하십시오.

예제 입력 2

5 7 0
0 0 0 8 0 0 0
0 7 6 5 9 7 0
0 0 0 5 9 6 0
9 4 0 4 4 7 0
0 0 0 9 8 6 0

예제 출력 2

3

참고 2

두 번째 예제 테스트에서 출력에는 새로운 요금표 제안이 포함되어 있지 않은데, 이는 요금 징수 체계 재구성 프로젝트가 아직 예비 단계에 있기 때문입니다.

서브태스크

• 전체 점수의 절반에 해당하는 테스트에서는 $q = 0$ 조건이 성립합니다.
• 나머지 테스트에서는 항상 $q = 1$ 조건이 성립합니다.

*비토시아에서 바이트시아로 향하는 방향은 당신의 관심사가 아닙니다. 그 방향은 적대적인 우호 국가의 사절이 관리합니다.