After years of pointless war, the Big Herring and the Small Herring have finally signed a peace treaty. To symbolize the complete reconciliation between the two nations, a highway has been built from the capital of the Herring Kingdom to the capital of the Small Herring Kingdom, and you have been appointed to manage the toll stations on this highway.
There are a total of $m$ toll stations on this highway, with the first toll station located at the start of the highway and the last toll station located at the end. A day is divided into $n$ hours, and the toll for passing through the $j$-th toll station during the $i$-th hour is $c_{i,j}$ "Herring Coins." It is worth noting that this fee may vary at different times of the day and can even be negative (in which case it represents a reward given to the driver).
The entire highway is so short that it can be traversed in its entirety within one hour. Of course, drivers do not necessarily have to rush; they may stop and rest any number of times along the way, but they cannot stay overnight on the highway, and all toll stations must be passed on the same day.
To maintain the peace treaty signed by the two Herring nations, the governments have jointly determined all possible optimal travel costs. Specifically, if a driver passes the first toll station at hour $i$ and arrives at the last toll station at hour $j$, the minimum possible cost is $f(i,j)$. As the highway manager, you cannot change these costs. However, you are allowed to adjust the toll rates of the intermediate toll stations, or even close some of them, provided that:
- The first and last toll stations must remain open;
- All minimum costs $f(i,j)$ must not change due to your adjustments;
- The new toll rates must be integer amounts of Herring Coins.
To minimize maintenance costs, you wish to close as many toll stations as possible. Determine the minimum number of toll stations that must be kept without changing any $f(i,j)$.
The toll station reorganization project is divided into two phases:
- Phase 1 ($q=0$): Only provide the minimum number of toll stations that must be kept.
- Phase 2 ($q=1$): Also provide the specific new toll rate scheme.
Input
The first line contains three integers $n, m, q$ ($2 \le n, m \le 30000; n \cdot m \le 300000; q \in \{0,1\}$), representing the number of hours in a day, the number of toll stations on the highway, and the current project phase, respectively.
The next $n$ lines each contain $m$ integers $c_{i,1}, c_{i,2}, \dots, c_{i,m}$ ($-10^6 \le c_{i,j} \le 10^6$), representing the toll for passing the $j$-th toll station during the $i$-th hour.
Output
Output a single integer $k$ ($2 \le k \le m$), representing the minimum number of toll stations that must be kept while satisfying all constraints.
If $q=1$, you must also output the new toll scheme, consisting of $n$ lines, each containing $k$ integers $d_{i,1}, d_{i,2}, \dots, d_{i,k}$ ($-10^{12}\le d_{i,j}\le 10^{12}$), representing the toll for passing the $j$-th kept toll station during the $i$-th hour.
Note: The toll situation for the direction from the "Small Herring Kingdom" to the "Herring Kingdom" is not within your scope of responsibility and is managed by friendly envoys sent by the "Big Herring Kingdom."
Examples
Input 1
7 7 0 7 -13 4 -6 -14 1 -3 13 -14 6 -7 -15 12 -2 12 -14 5 -6 -10 11 -15 -6 -14 6 -1 -9 9 12 7 -14 7 0 -11 7 -5 9 -15 10 -3 -12 5 7 1 -13 7 -5 -14 3 9
Output 1
6
Subtasks
Subtask 1 (3 points)
$q = 0$
Subtask 2 (4 points)
No additional restrictions.