Skyscraper Construction Order

On a 2D plane, there are \( n \) grid cells where skyscrapers are planned to be built. The \( i\)-th planned skyscraper is located at \( (r_i, c_i) \). You may choose any order to build them provided that the following conditions hold:

• Let \( s \) be a permutation of \( \{1,2,\dots,n\} \) representing the build order. For every \( 2 \le i \le n \), the cell \( (r_{s_i}, c_{s_i}) \) must share at least one common edge or a common corner with at least one of the previously built skyscrapers.
• For every \( 1\leq i\leq n \), when building the \( s_i \)-th skyscraper, there must exist a path (moving only to cells sharing a common edge) from cell \( (r_{s_i}, c_{s_i}) \) to the boundary of the 2D plane such that on this path no cell (other than \( (r_{s_i}, c_{s_i}) \)) contains a already built skyscraper.

In addition, an integer \( t \) is given:

• If \( t = 1 \), you need to output any valid build order.
• If \( t = 2 \), you need to output the build order whose reverse \( (s_n, s_{n-1}, \dots, s_1) \) is lexicographically maximum.

Note: All formulas are written in \( \LaTeX \) format.

inputFormat

The first line contains two integers \( n \) and \( t \) (the number of skyscrapers and the type of output, respectively). Each of the next \( n \) lines contains two integers \( r_i \) and \( c_i \) representing the coordinates of the planned skyscraper.

outputFormat

If \( t = 1 \), output any valid build order as a sequence of \( n \) integers (1-indexed) separated by spaces. If \( t = 2 \), output the lexicographically maximum (when reversed) build order in the reversed order, i.e. output \( s_n, s_{n-1}, \dots, s_1 \).

sample

1 1
0 0

1