Bajtocja 和 Bitocja 在經歷了多年毫無意義的戰爭後，終於簽署了和平條約。為了象徵兩國首都之間的最終和解，一條高速公路已經建成。你被任命為從 Bajtocja 通往 Bitocja 方向的高速公路路段的管理者。
目前高速公路上有 $m$ 個收費站，依序編號為 $1$ 到 $m$。第一個收費站位於高速公路起點，最後一個位於終點。通過特定收費站的費用可能會隨一天中的不同時間而有所不同。一天被分為 $n$ 個小時，編號為 $1$ 到 $n$。目前在 $i$ 時通過 $j$ 號收費站的費用為 $c_{i,j}$ 個 bajtalar。其中一些費用可能為 $0$（此時通過收費站免費），甚至為負數（此時駕駛通過收費站會獲得 $-c_{i,j}$ 個 bajtalar）。
整條高速公路非常短，可以在一小時內開完全程。當然，駕駛不需要這麼趕——在行駛過程中可以進行任意多次停留。然而，不能在高速公路上過夜；必須在同一天內通過所有收費站。
顯然，駕駛希望以盡可能低的成本通過高速公路。對於 $1 \le i \le j \le n$，我們用 $f(i, j)$ 表示如果駕駛在 $i$ 時通過第一個收費站，並在 $j$ 時通過最後一個收費站時，通過整條高速公路的最小可能總成本。所有 $f(i, j)$ 的值都已由兩國政府在和平條約中確定，因此作為高速公路管理者，你不能更改它們。然而，你可以隨意修改各個收費站的通行費率，甚至可以完全關閉部分收費站，前提是第一個和最後一個收費站必須保持開放，且 $f(i, j)$ 的值保持不變，並且你設定的所有費用都必須是 $1$ bajtalar 的整數倍。
為了最小化高速公路的維護成本，你希望關閉盡可能多的收費站。請計算為了繼續滿足條約條件，必須保持開放的收費站的最小數量。
收費站收費方案的重組計畫將分為兩個階段。在第一階段——初步設計——你只需要找到最佳的收費站數量。但在第二階段——實施階段——你還必須為剩餘的收費站提供一份完整的範例費率表。
輸入格式
輸入的第一行包含三個整數 $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$ 號收費站的費用，單位為 bajtalar。如果 $c_{i,j}$ 為負數，則表示駕駛在 $i$ 時通過第 $j$ 個收費站時會獲得 $-c_{i,j}$ 個 bajtalar。
輸出格式
輸出的第一行應包含一個整數 $k$ ($2 \le k \le m$)，表示為了使任何 $f(i, j)$ 的值都不改變，必須保留在高速公路上的收費站的最小數量。如果 $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
輸入 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
說明
在第一個範例測試中，通過高速公路的各個最小成本如下： $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}$ 費用下這些收費站不收取任何費用，第一個和最後一個收費站也不能被關閉。
在第二個範例測試中，輸出不包含新費率表的建議，因為收費方案的重組計畫僅處於初步階段。
子任務
- 在價值一半分數的測試中，滿足條件 $q = 0$。
- 在其餘測試中，始終滿足條件 $q = 1$。