After the HURRICANE team cut all the necessary $n \times m$ distinct parts during their internship, they needed to assemble them into usable products. It is known that each product consists of $m$ parts, and each part is exactly one component. Due to structural differences, when assembling a specific part of a product, one can only choose a component designed for that part (one can choose any one of the $n$ components to install; note: the installation time for each component may vary, and each component can only be installed once), and cannot choose a component designed for other parts.

There are $n$ assembly lines in the factory that can start the assembly process of $n$ products simultaneously. Considering that different components may require different assembly times, one can choose an appropriate assembly plan to minimize the time taken by the assembly line that finishes last.

Your task is to find such an assembly plan.

Description

Your program must provide 10 outputs corresponding to the 10 inputs we provide:

• The input includes the number of products to be completed $n$, the number of parts $m$ that make up a product, and the installation time for each component in each part.
• You need to find a plan such that each component is used exactly once as a part in a product, and the longest assembly time among all products is minimized. We define the assembly time of a product as the sum of the assembly times of all its $m$ parts.
• Then you need to output the plan to the corresponding output file in the format specified below.

Input

The provided input files are assembly1.in ~ assembly10.in. The first line of each file contains two integers, representing the number of products to be completed $n$ and the number of parts per product $m$.

The following $n$ lines each contain $m$ non-negative integers, forming an $n \times m$ matrix. The number in the $j$-th column of this matrix represents the assembly time required for each of the $n$ components for the $j$-th part.

Output

You need to complete assembly1.out ~ assembly10.out for our input files respectively. The first line of each file contains only one integer, representing the time taken by the assembly line that finishes last.

The following $n$ lines each contain $m$ non-negative integers, forming an $n \times m$ matrix, where the number in the $i$-th row and $j$-th column represents the assembly time of the component used by the $i$-th assembly line for the $j$-th part.

Examples

Input 1

3 3 
5 4 3 
3 0 5 
4 3 0

Output 1

9 
5 4 0 
4 0 5 
3 3 3

Note

The input indicates that three products need to be completed, and each product includes three parts. The assembly times for the three components used for the first part are 5, 3, and 4. The assembly times for the three components used for the second part are 4, 0, and 3. The assembly times for the three components used for the third part are 3, 5, and 0.

The output indicates: 9 is the time taken by the assembly line that finishes last. The first assembly line needs to assemble three components with times 5, 4, and 0. The second assembly line needs to assemble three components with times 4, 0, and 5. The third assembly line needs to assemble three components with times 3, 3, and 3.

Subtasks

This is a "submit answer" problem. For the 10 provided input files, you need to submit the corresponding output files. We will check your submitted output according to the format above. If it does not conform to the format, you will receive 0 points. Otherwise, we will score your submitted output according to the following criteria:

• If your output plan does not match the output assembly time, you will receive 0 points.
• We have specified a maximum assembly time for each test case. If the assembly time of your program's output is greater than this time, you will receive 0 points.
• Otherwise, your program will be scored according to the following formula:

$$score = \left\lfloor \frac{zero\_limit - your\_result}{zero\_limit - best\_result} \times 10\% \right\rfloor$$

Where $zero\_limit$ is the maximum assembly time we specified, $your\_result$ is your assembly time, and $best\_result$ is the known best assembly time.