Bajtocja i Bitocja po latach bezsensownych wojen wreszcie podpisały traktat pokojowy. Na znak ostatecznej zgody pomiędzy stolicami państw została wybudowana autostrada. Ty zaś zostałeś wyznaczony na zarządcę nitki autostrady prowadzącej z Bajtocji w kierunku Bitocji.

Na autostradzie aktualnie znajduje się $m$ bramek poboru opłat, ponumerowanych kolejno liczbami od $1$ do $m$. Pierwsza z nich znajduje się na początku autostrady, a ostatnia – na końcu. Koszty przejazdu przez daną bramkę mogą być różne o różnych porach dnia. Doba jest podzielona na $n$ godzin, ponumerowanych liczbami od $1$ do $n$. Aktualnie koszt przejazdu przez bramkę $j$ o godzinie $i$ wynosi $c_{i,j}$ bajtalarów. Niektóre spośród tych kosztów mogą być równe $0$ (przejazd przez bramkę jest wtedy darmowy) lub nawet ujemne (kierowca wtedy otrzymuje $-c_{i,j}$ bajtalarów za przejazd bramką).

Cała autostrada jest na tyle krótka, że można przejechać ją w przeciągu jednej godziny. Jednak oczywiście nie trzeba się tak śpieszyć – w trakcie przejazdu można zrobić dowolnie wiele postojów. Nie można jednak nocować na autostradzie; przez wszystkie bramki trzeba przejechać tego samego dnia.

Oczywiście kierowcy chcą przejechać autostradę możliwie małym kosztem. Przez $f(i, j)$ dla $1 \le i \le j \le n$ oznaczamy minimalny możliwy koszt przejechania całej autostrady, jeśli przez pierwszą bramkę kierowca przejedzie w godzinie $i$, a przez ostatnią bramkę w godzinie $j$. Wszystkie wartości $f(i, j)$ zostały ustalone w traktacie pokojowym przez rządy obu państw, więc jako zarządca autostrady nie możesz ich zmienić. Możesz jednak dowolnie modyfikować cenniki przejazdu przez poszczególne bramki lub nawet zupełnie zamknąć część bramek, o ile pierwsza i ostatnia bramka pozostaną otwarte, wartości $f(i, j)$ nie ulegną zmianie oraz wszystkie ustalone przez Ciebie koszty będą całkowitymi wielokrotnościami jednego bajtalara.

Aby zminimalizować koszty utrzymania autostrady, chciałbyś zamknąć jak najwięcej bramek. Wyznacz minimalną liczbę bramek, jakie muszą pozostać otwarte, aby nadal spełniać warunki traktatu.

Projekt reorganizacji schematu poboru opłat będzie składał się z dwóch faz. W pierwszej fazie – wstępnym projekcie – wystarczy, że znajdziesz samą optymalną liczbę bramek. Jednak w drugiej fazie – fazie wdrożenia projektu – musisz dodatkowo podać cały przykładowy cennik dla pozostawionych bramek.

Dữ liệu vào

Trong dòng đầu tiên của dữ liệu vào có ba số nguyên $n, m$ và $q$ ($2 \le n, m \le 30\,000$; $n \cdot m \le 300\,000$; $q \in \{0, 1\}$), lần lượt biểu thị số giờ trong một ngày, số lượng trạm thu phí hiện tại trên đường cao tốc và một bit mô tả giai đoạn của dự án. Giá trị $q = 0$ có nghĩa là giai đoạn đầu của dự án (thiết kế sơ bộ), trong khi giá trị $q = 1$ có nghĩa là dự án đang trong giai đoạn triển khai.

$n$ dòng tiếp theo chứa mô tả các khoản phí hiện tại; dòng thứ $i$ chứa $m$ số nguyên $c_{i,1}, c_{i,2}, \dots, c_{i,m}$ ($-10^6 \le c_{i,j} \le 10^6$). Giá trị $c_{i,j}$ là chi phí đi qua trạm $j$ vào giờ $i$ tính bằng bajtalar. Nếu giá trị $c_{i,j}$ âm, thì khi đi qua trạm thứ $j$ vào giờ $i$, người lái xe sẽ nhận được $-c_{i,j}$ bajtalar.

Dữ liệu ra

Dòng đầu tiên của dữ liệu ra phải chứa một số nguyên $k$ ($2 \le k \le m$), biểu thị số lượng trạm tối thiểu cần giữ lại trên đường cao tốc để không có giá trị $f(i, j)$ nào bị thay đổi. Nếu $q = 0$, dữ liệu ra chỉ nên bao gồm một dòng duy nhất chứa số này.

Nếu $q = 1$, trong $n$ dòng tiếp theo phải chứa một bảng giá ví dụ tối ưu thỏa mãn các điều kiện của bài toán. Trong dòng thứ $i$ của các dòng này phải chứa $k$ số nguyên $d_{i,1}, d_{i,2}, \dots, d_{i,k}$ ($-10^{12} \le d_{i,j} \le 10^{12}$). Giá trị $d_{i,j}$ biểu thị chi phí mới khi đi qua trạm thứ $j$ trong số các trạm được giữ lại vào giờ $i$.

Có thể chứng minh rằng với các giới hạn của bài toán, luôn có thể xác định các chi phí là số nguyên có giá trị tuyệt đối không vượt quá $10^{12}$.

Ví dụ

Ví dụ 1

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

3
0 0 0
0 1 0
0 0 0

Ví dụ 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

3

Ghi chú

Giải thích ví dụ: Trong bài kiểm tra ví dụ đầu tiên, các chi phí tối thiểu riêng lẻ để đi qua đường cao tốc như sau: $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$.

Không thể đạt được các chi phí đi lại tương tự khi chỉ sử dụng hai trạm. Lưu ý rằng trạm đầu tiên và trạm cuối cùng không thể bị đóng, mặc dù với các chi phí $d_{i,j}$ được đề xuất, không có khoản phí nào được thu tại các trạm này.

Trong bài kiểm tra ví dụ thứ hai, dữ liệu ra không chứa đề xuất về bảng giá mới vì dự án tái cơ cấu hệ thống thu phí mới chỉ đang ở giai đoạn sơ bộ.

Nhiệm vụ con

• Trong các bài kiểm tra chiếm một nửa số điểm, điều kiện $q = 0$ được thỏa mãn.
• Trong các bài kiểm tra còn lại, điều kiện $q = 1$ luôn được thỏa mãn.