Autostrada Toll Station Optimization

After years of meaningless war, Byteotia and Bitotia signed a peace treaty. As a symbol of the final agreement, a highway was built between the two capitals. You are appointed as the manager for the highway in the Byteotia → Bitotia direction (the reverse direction is managed by an unfriendly country).

The highway has m toll stations numbered from 1 to m. The day is divided into n hours (numbered 1 to n), and the fee at toll station j during hour i is given as \(c_{i,j}\) bytealerts. Note that some fees might be 0 (free) or even negative (in which case the driver receives \(-c_{i,j}\) bytealerts).

The highway is so short that one can drive through it in one hour. Moreover, you are allowed to stop arbitrarily during the journey (although you cannot overnight on the highway – you must complete the journey on the same day). Drivers, however, wish to pay as little as possible. For every pair \(1 \le i \le j \le n\), let \(f(i,j)\) denote the minimum possible total fee to pass through the entire highway when the driver passes the first toll station during hour \(i\) and the last toll station during hour \(j\). (All the values \(f(i,j)\) have been pre‐set by the governments in the peace treaty so that you cannot change them.)

You are given some freedom. As long as you retain the first and last toll stations, preserve all the values \(f(i,j)\) (and all fees remain integer multiples of 1 bytealert), you are allowed to change the fees at any toll station arbitrarily – even cancel some of the toll stations.

In order to minimize maintenance costs, you want to cancel as many toll stations as possible while still satisfying the treaty requirements. In the first stage (the preliminary design phase) you only need to determine the optimal (i.e. minimal) number of toll stations that must be kept. In the second stage (the implementation phase) you must also provide a full toll pricing plan.

Task: Given the fee table \(c_{i,j}\) for a highway with m toll stations and n hours in a day, determine the minimum number of toll stations that must be preserved (note that toll stations 1 and m cannot be cancelled) so that there exists some assignment of toll fees for the preserved toll stations which still produces the same function \(f(i,j)\) for all \(1\le i\le j\le n\). In addition, provide a valid toll pricing plan for the preserved stations. (It is allowed to leave the toll fees unchanged.)

Note: The original fee table guarantees that for any 1 ≤ i ≤ j ≤ n, the minimum total cost if one passes the toll stations in order, choosing the passing hour for each station (subject to non‐decreasing hours), is \(f(i,j)\). Your pricing plan must preserve these values.

Input Format:

• The first line contains two integers \(n\) and \(m\) (the number of hours per day and the number of toll stations, respectively).
• The next \(n\) lines each contain \(m\) integers. The \(j\)th number in the \(i\)th line is \(c_{i,j}\) – the fee at toll station \(j\) if passed during hour \(i\).

Output Format:

• On the first line, output a single integer representing the minimum number of toll stations that must be preserved.
• Then, output the full toll pricing plan for the preserved toll stations. For each preserved toll station (in order from 1 to m), output a line containing n space‐separated integers – the fee assigned for that toll station for hours 1 through n. (You may output any valid plan that satisfies the treaty conditions.)

Important: It is guaranteed that all values in the pricing plan must be integer multiples of 1 bytealert. Moreover, the original table always yields valid values \(f(i,j)\). You are allowed to keep the pricing plan unchanged if it meets the conditions.

Example:

Input:
2 2
1 2
3 4
Output:
2
1 3
2 4

</p>

inputFormat

The first line contains two integers n and m – the number of hours and toll stations, respectively. The next n lines each contain m integers; the jth integer in the ith line represents \(c_{i,j}\), the fee (in bytealerts) for toll station j when passed during hour i.

outputFormat

On the first line, output a single integer – the minimum number of toll stations that must be preserved. Then output the full toll pricing plan for these stations in order: for each preserved toll station, output a line consisting of n space‐separated integers. The plan must guarantee that for every \(1 \le i \le j \le n\), the minimum total fee for a journey (computed with the preserved stations and their corresponding pricing) is exactly \(f(i,j)\) as determined by the original plan.

sample

2 2
1 2
3 4

2
1 3
2 4

</p>