3394: F.Sorting

Bobo has n tuples (a1, b1, c1), (a2, b2, c2), . . . , (an, bn, cn). He would like to find the lexicographically smallest permutation p₁, p₂, . . . , p_n of 1, 2, . . . , n such that for i {2, 3, . . . , n} it holds that

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n. The i-th of the following n lines contains 3 integers ai, b_i and c_i.

For each test case, print n integers p₁, p₂, . . . , p_n seperated by spaces. DO NOT print trailing spaces.

Constraint

• 1 ≤ n ≤ 10³

• 1 ≤ a_i, b_i, c_i ≤ 2 × 10⁹

• The sum of n does not exceed 10⁴.

2
1 1 1
1 1 2
2
1 1 2
1 1 1
3
1 3 1
2 2 1
3 1 1

2 1
1 2
1 2 3