Byteotia and Bitotia have finally signed a peace treaty after years of senseless wars. To mark the final reconciliation, a highway has been built between the capitals of the two countries. You have been appointed as the manager of the highway segment leading from Byteotia towards Bitotia.*

There are currently $m$ toll gates on the highway, numbered sequentially from $1$ to $m$. The first one is at the beginning of the highway, and the last one is at the end. The costs of passing through a given gate can vary at different times of the day. The day is divided into $n$ hours, numbered from $1$ to $n$. Currently, the cost of passing through gate $j$ at hour $i$ is $c_{i,j}$ bajtalars. Some of these costs may be equal to $0$ (passing through the gate is then free) or even negative (the driver then receives $-c_{i,j}$ bajtalars for passing through the gate).

The entire highway is short enough that it can be traversed within one hour. However, there is no need to rush — you can make any number of stops during the journey. You cannot, however, spend the night on the highway; you must pass through all gates on the same day.

Naturally, drivers want to traverse the highway at the lowest possible cost. Let $f(i, j)$ for $1 \le i \le j \le n$ denote the minimum possible cost of traversing the entire highway if the driver passes through the first gate at hour $i$ and through the last gate at hour $j$. All values of $f(i, j)$ have been set in the peace treaty by the governments of both countries, so as the highway manager, you cannot change them. However, you can freely modify the toll prices for individual gates or even completely close some gates, provided that the first and last gates remain open, the values of $f(i, j)$ do not change, and all costs you set are integer multiples of one bajtalar.

To minimize the costs of maintaining the highway, you would like to close as many gates as possible. Determine the minimum number of gates that must remain open to still satisfy the conditions of the treaty.

The reorganization project for the toll collection scheme will consist of two phases. In the first phase — the preliminary design — it is sufficient to find only the optimal number of gates. However, in the second phase — the implementation phase — you must additionally provide a full example price list for the remaining gates.

Input

The first line of input contains three integers $n$, $m$, and $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 current number of toll gates on the highway, and a bit describing the project phase, respectively. The value $q = 0$ denotes the first stage of the project (preliminary design), while $q = 1$ denotes that the project is already in the implementation phase.

The next $n$ lines contain the description of the current tolls; the $i$-th of these lines contains $m$ integers $c_{i,1}, c_{i,2}, \dots, c_{i,m}$ ($-10^6 \le c_{i,j} \le 10^6$). The value $c_{i,j}$ denotes the cost of passing through gate $j$ at hour $i$ expressed in bajtalars. If the value $c_{i,j}$ is negative, the driver receives $-c_{i,j}$ bajtalars for passing through the $j$-th gate at hour $i$.

Output

The first line of output should contain a single integer $k$ ($2 \le k \le m$), representing the minimum number of gates that must be left on the highway so that no value of $f(i, j)$ changes. If $q = 0$, the output should consist of only one line containing this single number.

If $q = 1$, the next $n$ lines should contain an example optimal toll price list satisfying the conditions of the problem. The $i$-th of these lines should contain $k$ integers $d_{i,1}, d_{i,2}, \dots, d_{i,k}$ ($-10^{12} \le d_{i,j} \le 10^{12}$). The value $d_{i,j}$ denotes the new cost of passing through the $j$-th of the remaining gates at hour $i$.

It can be proven that for the constraints of the problem, it is always possible to determine costs that are integers whose absolute values do not exceed $10^{12}$.

Examples

Input 1

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

Output 1

3
0 0 0
0 1 0
0 0 0

Input 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 2

3

Note

In the first example test, the individual minimum costs of traversing the highway are as follows: $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$.

It is impossible to achieve the same traversal costs using only two gates. Note that the first and last gates cannot be closed, even though no tolls are collected at these gates with the proposed costs $d_{i,j}$.

In the second example test, the output does not contain a proposal for a new price list, as the reorganization project for the toll collection scheme is only in the preliminary phase.

Subtasks

• In tests worth half the points, the condition $q = 0$ holds.
• In the remaining tests, the condition $q = 1$ always holds.

*The direction from Bitotia to Byteotia does not concern you; it is managed by an envoy of a hostile friendly country.