Sorting tuples
Let's define a tuple of length M as an ordered collection of M natural numbers (x_1, x_2, x_3, ..., x_M). The order of numbers in a tuple is fixed, meaning you cannot rearrange them. You will be provided with a set of N tuples, each having the same length. Your task is to sort these tuples in non-decreasing order.
To accomplish this, use the following rule to compare tuples: A tuple (x_1, x_2, x_3, ..., x_M) is considered strictly less than another tuple (y_1, y_2, y_3, ..., y_M) if there exists an index K such that for all indices 1 ≤ i < K, x_i = y_i, and at index K, x_K < y_K. In other words, the first K-1 elements of both tuples are identical, and the K-th element of the first tuple is less than that of the second.
For example, the tuple (3, 5, 6, 7, 6, 9) is strictly less than the tuple (3, 5, 6, 9, 1, 1), because the first three elements are the same, and the fourth element of the first tuple is less than that of the second.
The tuples (4, 1, 2, 2, 1) and (4, 1, 2, 2, 1) are equal, while the tuple (5, 2, 3, 6, 8, 6, 7) is strictly greater than the tuple (5, 2, 1, 9, 3, 3, 7).
Here are additional examples of tuple comparisons:
- (1, 2, 3, 4, 5) < (1, 2, 3, 4, 7) - (4, 6, 3, 2, 5) > (2, 9, 9, 9, 9) - (5, 4, 4) < (6, 3, 3) - (5, 4, 4) > (5, 3, 5) - (4, 3, 2, 4, 5, 5) = (4, 3, 2, 4, 5, 5)
Input
The first line of the input file contains two natural numbers N and M, separated by a space. N is the number of tuples (1 ≤ N ≤ 1000000), and M is the number of elements in each tuple (1 ≤ M ≤ 10). The next N lines each contain M numbers separated by spaces, representing the elements of a tuple. Each element is an integer between 1 and 9, inclusive.
Output
Output all tuples in non-decreasing order to the output file. Each tuple should be printed on a separate line, with elements separated by a single space. The first line should contain the first tuple in order, and the last line should contain the last one.