本题与 Maximal Angle 相同，但数据范围更大。

平面上有 $n$ 个点 $A_1, \ldots, A_n$，其中任意三点不共线。

对于每对 $(i, j)$（$1 \leq i < j \leq n$），你需要找到一个不同于 $i$ 和 $j$ 的下标 $k$，使得角 $A_i A_k A_j$ 最大。

输入格式

第一行包含一个整数 $n$（$3 \leq n \leq \textbf{5000}$）。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，表示点 $A_i$ 的坐标（$-10^9 \leq x_i, y_i \leq 10^9$）。

保证所有点互不相同，且任意三点不共线。

还保证除样例外的所有测试数据均按以下方式生成：评测人员先选定点的初始位置，然后将每个点的每个坐标增加一个 $0$ 到 $1000$ 之间的随机数。如果生成的测试数据无效，则重新开始生成。

输出格式

输出 $n - 1$ 行。

第 $i$ 行应包含 $i$ 个整数。第 $i$ 行的第 $j$ 个数应为点对 $(j, i + 1)$ 的答案。

如果存在多个满足条件的答案，输出其中任意一个即可。

样例

输入样例 1

4
0 0
1 0
0 1
-1 -1

输出样例 1

3
2 1
2 1 1