Sort Recovery

Bob has a table of numbers, with $R$ rows and $C$ columns. The table has already been sorted in some specific order, but he's forgotten how! Therefore, Bob has asked you, a sort recovery specialist, for help.

We will define a sort as a series of $C$ column indices and sorting orders ("asc" or "desc"). For example, a table with 3 columns could be sorted as "2 asc, 1 desc, 3 asc". In this case, the rows of the table would be ordered primarily by their second column in ascending order. If there are tied rows, they would be broken by their first column, in descending order, then by their third column, in ascending order.

Help Bob by finding a possible sort that could have produced his table. It is guaranteed that such a sort will always exist.

Input

The first line will contain two space-separated integers, $R$ and $C$ ($2 \le R, C \le 2000$), the number of rows and columns in the table respectively.

The following $R$ lines will each contain $C$ space-separated integers, describing the contents of Bob's table. Each of these integers will be between 0 and 1000.

Output

You should output $C$ lines, representing a possible sort of the table. Each line should contain a column index from $1$ to $C$, followed by either asc or desc, representing the sorting direction for that column. Each column index must occur exactly once in the sort.

If there are multiple solutions, you may print any of them.

Subtasks

• Subtask 1 (20%): $C = 2$
• Subtask 2 (20%): $R, C \le 5$
• Subtask 3 (30%): $R, C \le 250$
• Subtask 4 (30%): No further restrictions apply.

Warning: Subtask 4 contains cases with very large amounts of input data. If you believe you have a fast enough algorithm, but are still receiving Time Limit Exceeded verdicts in only subtask 4, this might be due to slow I/O performance – see this document for tips on how to improve this.

Sample Explanation

In the first sample case, there is only one possible sort – rows must have been sorted by the first column in ascending order, then by the second column in descending order (to break the tie between rows 3 and 4).

In the second sample case, note that "2 asc, 3 asc, 1 desc" is also a valid solution.