AT_abc448_f [ABC448F] Authentic Traveling Salesman Problem

$ 2 $ 次元平面上に $ 1 $ から $ N $ の番号がついた $ N $ カ所の地点があります。地点 $ i $ は座標 $ (X_i, Y_i) $ にあります。 あなたは地点 $ 1 $ を出発して全ての地点をちょうど $ 1 $ 回ずつ巡回して再び地点 $ 1 $ に戻ることにしました。 ここで、地点 $ i $ から地点 $ j $ へ移動するには $ \vert X_i - X_j \vert + \vert Y_i - Y_j \vert $ 秒かかります。 地点 $ 1 $ を出発してから $ 10^{10} $ 秒以内に全ての地点を巡回して再び地点 $ 1 $ に戻ることができる経路を出力してください。なお、制約下においてこの条件を満たす経路が少なくとも $ 1 $ つ存在することが保証されます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_N $ $ Y_N $

$ i $ $ (1 \leq i \leq N) $ 番目に訪問する地点を $ p_i $ として以下の形式で答えを出力せよ。 > $ p_1 $ $ p_2 $ $ \dots $ $ p_N $ 出力された答えは、以下の条件を全て満たす時に正答とみなされる。 - $ (p_1, p_2, \dots, p_N) $ は $ (1, 2, \dots, N) $ の順列 - $ p_1 = 1 $ - $ d(i, j) $ を地点 $ i $ から地点 $ j $ へ移動する時にかかる秒数としたとき、 $ \displaystyle \sum_{i=1}^N d(p_i, p_{(i \bmod N) + 1} ) \leq 10^{10} $ 答えが複数ある場合はどれを出力しても正解とみなされる。

### Sample Explanation 1 $ \displaystyle \sum_{i=1}^N d(p_i, p_{(i \bmod N) + 1}) = 4 + 2 + 4 = 10 $ であるため出力は条件を満たします。 ### Constraints - $ 1 \leq N \leq 6 \times 10^4 $ - $ 0 \leq X_i \leq 2 \times 10^7 $ - $ 0 \leq Y_i \leq 2 \times 10^7 $ - $ i \neq j $ ならば $ (X_i, Y_i) \neq (X_j, Y_j) $ - 入力される値は全て整数