#492 Tour

Loading problem...

Preparing the statement, recent submissions, and submit form.

#492 Tour

Authors: pk661

Time limit: 1000 ms
Python time limit: 2000 ms
Memory limit: 1024 MB
Checker: CUSTOM
Solve threshold: 100

Statement

Statement language

There are $N$ points numbered $1$ through $N$ on a two-dimensional plane. Point $i$ ( $1\le i\le N$ ) has coordinates $(X_i,Y_i)$ . Let $D$ be the maximum distance between two points.

For a permutation $Q=(Q_1,Q_2,\cdots,Q_N)$ of , define the length of the tour represented by this permutation as follows. Here, .

L=\sum_{i=1}^{N}\sqrt{(X_{Q_i}-X_{Q_{i+1}})^2+(Y_{Q_i}-Y_{Q_{i+1}})^2}.

Choose the permutation $Q$ so that $\frac{L}{D}$ is small. See the Scoring section for details.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print a permutation $(Q_1,Q_2,\cdots,Q_N)$ of on one line.

Constraints

$1\le T\le200\,000$ .
$3\le N\le200\,000$ .
$- 10^{}$ ().

Subtasks

#	Score	Constraints
1	5	$N\le18$ .
2	95	No additional constraints.

Scoring

For each test case in a subtask, compute the following value.

z=\displaystyle\frac{\frac{L}{D}-10}{\sqrt{N}}.

Samples

Input

Output

1 2 3
1 2 3 4

Editorial

View editorial

12

\leq

X_{i}

,

Y_{i}

\leq

10^{12}

-10^{12}\le X_i,Y_i\le10^{12}

Condition	Score
$Z>3$	$0$
$2<Z\le3$	$36$
$\sqrt{2}<Z\le2$	$58$
$\sqrt{\displaystyle\frac{\pi}{2}}<Z\le\sqrt{2}$
$Z\le\sqrt{\displaystyle\frac{\pi}{2}}$