Problem Description

Translated from PA 2024 Round 5 Autostrada 2

After years of meaningless wars, Byteotia and Bitotia have finally signed a peace treaty. As a symbol of the final agreement, a highway was built between the capitals of the two countries. You have been appointed as the manager of this highway from Byteotia to Bitotia direction (the direction from Bitotia to Byteotia is of no interest to you, as it is managed by the manager of an unfriendly country).

Currently, there are $m$ toll booths on the highway, numbered from $1$ to $m$. The cost to pass through a toll booth varies at different times of the day. The day is divided into $n$ hours, numbered from $1$ to $n$. Currently, the cost to pass through the $j$-th toll booth during the $i$-th hour is $c_{i,j}$ bytealerts. Some of these costs may be $0$ (the toll booth is free), or even negative (the driver receives $-c_{i,j}$ bytealerts).

The entire highway is short enough to be traversed in one hour. Of course, you don't have to rush, you can stop at will during the journey. However, you cannot stay overnight on the highway and must pass all toll booths within the day.

Naturally, drivers want to pass through the highway at the lowest possible cost. For $1 \le i \le j \le n$, we use $f(i,j)$ to denote the minimum possible cost for a driver to pass through the first toll booth at the $i$-th hour and the last toll booth at the $j$-th hour. All $f(i,j)$ are preset by the peace treaty of the two governments and cannot be changed by you as the highway manager.

However, as long as the first and last toll booths are retained, the values of $f(i, j)$ remain unchanged, and all set costs are integers of $1$ bytealert, you are free to modify the costs of passing through various toll booths, or even cancel some toll booths.

To minimize the maintenance cost of the highway, you want to cancel as many toll booths as possible. Determine the minimum number of toll booths that need to be retained to meet the treaty's requirements.

The toll plan restructuring project will be divided into two phases. In the first phase, the preliminary design phase, you only need to find the optimal number of toll booths. In the second phase, the implementation phase, you also need to provide a complete toll price table plan.

Input Format

The first line contains three integers $n, m, q\ (2 \le n, m \le 30,000, n \cdot m \le 300,000, q \in \{0, 1\})$, representing the number of hours in a day, the number of toll booths, and a bit describing the project phase. $q=0$ indicates the project is in the first phase (preliminary design), and $q=1$ indicates the project is in the second phase (implementation phase).

The next $n$ lines describe the current toll situation, where the $i$-th line contains $m$ integers $c_{i,1}, c_{i,2}, \ldots, c_{i,m}\ (-10^6 \le c_{i,j} \le 10^6)$, as described in the problem.

Output Format

The first line outputs an integer $k\ (2 \le k \le m)$, indicating the minimum number of toll booths that need to be retained to ensure no $f(i,j)$ changes. If $q=0$, the output contains only this integer.

If $q=1$, the next $n$ lines output the optimal price plan that meets the conditions of the problem. The $i$-th line contains $k$ integers $d_{i,1}, d_{i,2}, \ldots, d_{i,k}\ (-10^{12} \le d_{i,j} \le 10^{12})$. $d_{i,j}$ represents the new cost to pass through the $j$-th toll booth during the $i$-th hour.

It can be deduced from the problem constraints that there is always a plan with costs that are integers and whose absolute values do not exceed $10^{12}$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

3
0 0 0
0 1 0
0 0 0

Input Sample #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

Output Sample #2

3

Notes/Hints

• Half of the subtasks satisfy $q=0$.
• The other half of the subtasks satisfy $q=1$.

见题面 Input 部分

见题面 Output 部分