This task is the same as Maximal Angle but with larger constraint.

There are $n$ points $A_1$, $\ldots$, $A_n$ in the plane such that no three of them lie on a common line.

For each pair $(i, j)$ ($1 \leq i < j \leq n$) you have to find such index $k$ (different from $i$ and $j$) that the angle $A_i A_k A_j$ is the largest possible.

Input

The first line contains one integer $n$ ($3 \leq n \leq \textbf{5000}$).

$i$-th of the next $n$ lines contains two integer $x_i$ and $y_i$~--- coordinates of point $A_i$ ($-10^9 \leq x_i, y_i \leq 10^9$).

It is guaranteed that all points are distinct and no three points lie on a common line.

It is also guaranteed that all tests except for the sample cases were constructed in the following manner: jury chooses preliminary positions of the points, then each coordinate of each point is increased by a random number between $0$ and $1000$. If the resulting test is invalid, the generation starts over.

Output

Print $n - 1$ line.

$i$-th string should contain $i$ integers. $j$-th number of $i$-th string should be the answer for the pair $(j, i + 1)$.

If there are several valid answers, print any of them.

Example

Input

4
0 0
1 0
0 1
-1 -1

Output

3
2 1
2 1 1