Quadratic Functions and a Line

Time limit0.1sMemory limit1024 MB

Summary

Given N quadratics with leading coefficient 1 or -1, pick the fewest that make every line meet at least one of them, and print their indices or -1.

Level: Hard8 of 10
Topics: Geometry, Math, Greedy
Solved: No attempts yet

Problem

Azber and Biou play a game on a two-dimensional coordinate plane.

Before the game starts, Azber has $N$ quadratic functions that Azber can draw. The leading coefficient of each quadratic function Azber has is either $1$ or $-1$ .

At the beginning, Azber draws some of the quadratic functions on the coordinate plane.

If Biou can draw a line that meets none of the quadratic functions, Biou wins. If every line Biou draws meets at least one quadratic function, Azber wins.

If Azber can win, Azber wants to win by drawing the fewest possible quadratic functions on the coordinate plane.

Determine whether Azber can win. If Azber can, find the minimum number of quadratic functions that must be drawn on the coordinate plane, and find the quadratic functions Azber draws in that case.

Input

The first line contains the number $N$ of quadratic functions that Azber can draw. $(1 \le N \le 20\,000)$

The next $N$ lines each contain three integers $X_i$ , $Y_i$ , and $Z_i$ . $(1 \le i \le N;$ $|X_i|=1;$ $-5\,000 \le Y_i \le 5\,000;$ $-2.5 \times 10^7 \le Z_i \le 2.5 \times 10^7)$

This means the $i$ -th quadratic function Azber has is $y = X_i x^2 + Y_i x + Z_i$ .

Output

If Azber cannot win against Biou, print -1.

If Azber can win, print the minimum number of quadratic functions Azber uses on the first line. On the next line, print the numbers of the quadratic functions Azber uses, separated by spaces.

If several sets of the minimum size win, print any of them.

Examples3

Example 1
Input
```
2
1 0 1
-1 0 -1
```
Expected output
```
-1
```
Example 2
Input
```
2
1 0 -1
-1 0 1
```
Expected output
```
2
1 2
```

Example 3

Input

Expected output

3
2 3 4