C. Cattering
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Throughout heaven and earth, I alone am the catter one.

— Jack probably never said this.

After returning from catching grasshoppers, Jack finds his cat, Salmon, has brought $$$N$$$ of his friends(cats), numbered $$$1$$$ to $$$N$$$, to the house. He decides to prepare food for all the cats.

Aside from the food dedicated for Salmon, there are currently $$$M$$$ types of cat food in his house ($$$M \geq N$$$). Jack is a proud "catterer", a person who specializes in catering to cats. He can estimate how much happiness each cat has eating each type of food. Formally speaking, Jack can find a matrix $$$A$$$ size $$$N \times M$$$ where $$$A_{ij}$$$ is how much happiness cat $$$i$$$ has when eating food type $$$j$$$.

The problem is, cats refuse to have the same types of food. He must prepare one type of food among $$$M$$$ types for each of $$$N$$$ cats such that there are no pairs of cats that receive the same food. He wants to $$$\textbf{maximize the minimum happiness among all cats}$$$. That is, if cat $$$i$$$ gets the food type $$$p_i$$$, he wants to $$$\textbf{maximize}\ min(A_{1p_1},A_{2p_2},\dots,A_{Np_N})$$$. Help him find the way to prepare foods to achieve his objective.

Salmon blessed you good luck for the contest.
Input

The first line contains two integers $$$N, M\ (1 \leq N \leq M \leq 1,000)$$$ — the number of cats and the number of food types, respectively.

The $$$i^{th}$$$ of the following $$$N$$$ lines contains $$$M$$$ integers $$$A_{i1},A_{i2},\dots,A_{iM}\ (1 \leq A_{i1},A_{i2},\dots,A_{iM} \leq 10^9)$$$ — the happiness cat $$$i$$$ has eating food type $$$1,2,\dots,M$$$, respectively.

Output

For the first line, output one integer — the maximum value of the minimum happiness among all cats.

For the second line, output $$$N$$$ integers $$$p_1,p_2,\dots,p_N$$$ — the food type for cat $$$1,2,\dots,N$$$, respectively.

Examples
Input
3 3
1 2 3
1 3 2
3 1 2
Output
3
3 2 1
Input
3 4
3 1 1 2
2 3 1 1
3 3 1 1
Output
2
4 2 1
Note

In the first testcase, Jack can feed food type $$$3$$$ to cat $$$1$$$, food type $$$2$$$ to cat $$$2$$$, and food type $$$1$$$ to cat $$$3$$$. They will all have happiness value $$$3$$$.

In the second testcase, the minimum value cannot be $$$3$$$ because only cat food types $$$1$$$ and $$$2$$$ can make happiness value $$$3$$$. By giving food type $$$4,\ 2,\ 1,$$$ respectively, the happiness values will be $$$2,\ 3,\ 3,$$$ respectively, which makes the least happiness $$$2$$$.