#2739. 最远点

题目描述

给你一个N个点的凸多边形，求离每一个点最远的点。

输入格式

本题有多组数据，第一行一个数T，表示数据组数。
每组数据第一行一个数N，表示凸多边形点的个数，接下来N对数，依次表示1~N这N个点的坐标，按照逆时针给出。

输出格式

对于每组数据输出N个数，第i个数表示离第i个点最远的点的编号，如果有多个最远点，输出编号最小的。

样例

样例输入

1  

4  

0 0  

1 0  

1 1  

0 1  

样例输出

3  

4  

1  

2  

数据范围与提示

数据规模和约定

坐标的绝对值在1e9以内；

任意点对距离数值的平方不会超过long long；

令S为每组数据凸多边形点数之和；

对于20%的数据，S<=2000；

对于50%的数据，S<=50000；

对于100%的数据，S<=500000；

数据有梯度。