G. 琪露诺寻找锐角
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

二维平面内有 $$$n$$$ 个不同的点 $$$P_1(x_1,y_1),P_2(x_2,y_2),\cdots,P_n(x_n,y_n)\ (\forall i \in [1,n],x_i,y_i \in Z)$$$。你需要找到三个整数 $$$i,j,k\ (1 \le i,j,k \le n)$$$ 使得 $$$i \not = j, i \not = k, j \not = k$$$ 且 $$$\angle P_iP_jP_k$$$ 是锐角$$$^*$$$,或报告无解。

*锐角是指严格大于0°而严格小于90°的角。

Input

每个测试点包含多个测试用例。第一行包含一个整数 $$$t\ (1 \le t \le 10^5)$$$,表示测试用例的数量。

对于每个测试用例,第一行包含一个整数 $$$n\ (3 \le n \le 10^{5})$$$,表示点的数量。

接下来的 $$$n$$$ 行中,第 $$$i$$$ 行包含两个整数 $$$x_i,y_i\ (-10^9 \le x_i,y_i \le 10^9)$$$,表示第 $$$i$$$ 个点的坐标。保证 $$$n$$$ 个点坐标两两不同。

保证所有测试数据 $$$n$$$ 之和不超过 $$$10^5$$$。

Output

对于每个测试用例,如果不存在解,输出一行一个整数 -1;否则输出一行 3 个整数 $$$i,j,k$$$ 满足题意。

如果有多种合法答案,你可以输出任意一种。

Example
Input
2
3
1 1
0 0
2 2
3
0 0
1 0
0 1
Output
-1
1 2 3
Note

对于第 1 个测试点:

$$$\angle P_1P_2P_3 = 0°,\angle P_2P_1P_3 = 180°,\angle P_1P_3P_2 = 0°$$$。

所以无解。

对于第 2 个测试点:

$$$\angle P_1P_2P_3 = 45°$$$。