Egg Tart Queue Ordering

Alice and Bob are teaching children how to make egg tarts. Making an egg tart requires \(m\) different ingredients numbered from \(1\) to \(m\). For each egg tart, ingredient \(i\) is used in an amount of \(g_i\) grams.

There are \(n\) children (numbered from \(1\) to \(n\)). The \(i\)-th child has \(c_{i,j}\) grams of ingredient \(j\). Each child makes as many egg tarts as possible using their available ingredients. For each child, the number of egg tarts made is

[ T_i = \min_{1\le j\le m}\left\lfloor \frac{c_{i,j}}{g_j} \right\rfloor ]

After production, for each ingredient \(j\), the remaining amount for child \(i\) is

[ R_{i,j} = c_{i,j} - T_i \times g_j. ]

Now, the egg tarts are in the oven and the children must line up to receive their tarts. However, the ordering is decided according to the following rules:

1. Alice promotes thriftiness. She chooses one ingredient \(x\) (from \(1\) to \(m\)) and orders the children in increasing order of the remaining amount \(R_{i,x}\). Children with less remaining material \(x\) come first.
2. Bob values hard work. When two children have the same remaining amount of the chosen ingredient, the child who made more egg tarts comes earlier.
3. If both the remaining material and the number of egg tarts are the same, then the child with the smaller ID comes first.

You are not sure which ingredient Alice will choose. For each \(x = 1,2,\ldots,m\), output the order in which the children will stand in line.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n, m \le 10^5)\), representing the number of children and the number of ingredients.

The second line contains \(m\) integers \(g_1, g_2, \ldots, g_m\) \((1 \le g_j \le 10^9)\); \(g_j\) is the grams of ingredient \(j\) required for one egg tart.

Then \(n\) lines follow. The \(i\)-th of these lines contains \(m\) integers \(c_{i,1}, c_{i,2}, \ldots, c_{i,m}\) \((0 \le c_{i,j} \le 10^9)\); \(c_{i,j}\) is the grams of ingredient \(j\) available to child \(i\).

outputFormat

Output \(m\) lines. The \(x\)-th line (for \(x = 1, 2, \ldots, m\)) should contain \(n\) integers, representing the ordering of the children according to the criteria when ingredient \(x\) is chosen by Alice. The children should be listed by their IDs separated by a space.

sample

3 2
2 3
4 6
5 3
2 7

1 3 2
1 2 3