시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Let $p_0, p_1, \dots, p_{n-1}$ be $n$ points in the plane. We say that two points are friends if one can draw a circle that contains both points in its interior and all the other $n-2$ points in its exterior. Print the indices of the points that are friends with $p_0$.

It is guaranteed that there is no circumference containing $p_0$ and three or more other points. It is also guaranteed that there is no line containing $p_0$ and two or more other points.

입력

The first line contains an integer $t$, the number of test cases ($1 \leq t \leq 10^4$).

Each test case starts with a line containing an integer $n$ ($2 \leq n \leq 10^5$), the number of points. It is followed by $n$ lines, each one containing two integers $x_i$ and $y_i$ ($-10^{9} \leq x_i, y_i \leq 10^{9}$): the coordinates of the $i$-th point.

The tests are not explicitly targeting precision issues. In particular, it is guaranteed that, if we moved $p_0$ by a distance of at most $10^{-6}$ units in any direction, the answer would remain the same.

The total number of points in all test cases does not exceed $10^5$.

출력

For each test case, print a line containing one integer $m$, the number of friends of $p_0$, followed by $m$ integers: the indices of the friends of $p_0$ in lexicographical order.

예제 입력 1

2
4
1 0
3 1
3 -2
7 0
5
0 0
-2 -1
2 2
-2 10
-1 11

예제 출력 1

2 1 2
3 1 2 3