A set of $N$ double-sided mirrors are scattered on an integer coordinate plane uniformly at random. For simplicity, the $i^{th}$ mirror can be thought of as a point at $(x_i,y_i)$ with an infinitesimally small radius. You will fire a laser starting at one of the mirrors in the direction of a different mirror. When a laser hits a mirror, it will reflect off the mirror and continue in its new direction until it hits another mirror (or forever if it never hits another mirror).

We can describe the direction the laser is travelling in using a $2$-dimensional vector $(v,w)$. This represents the laser travelling in a direction that makes an angle equal to $\mathrm{arctan2}(w,v)$ relative to the $x$-axis.

Information on the $\mathrm{arctan2}$ function can be found here in C++, here in Java, and here in Python.

The reflection behaviour of the $i^{th}$ mirror can be described using $2$ integers $A_i$ and $B_i$. Suppose the current direction of the laser is $(v,w)$. When the laser hits the $i^{th}$ mirror, the direction of the laser changes to $(A_i\cdot v+B_i\cdot w,B_i\cdot v-A_i\cdot w)$. It is guaranteed that this represents a rotation of $180$ degrees, followed by a reflection across a line passing through the origin, and finally a scalar multiplication of the resulting vector.

Side Note: There is nothing special about this reflection behaviour; it works the same way as a conventional mirror. The purpose of providing $A_i$ and $B_i$ is to avoid floating point precision errors.

Can you determine if you can fire a laser starting at one of the mirrors in the direction of a different mirror, such that it hits at least $\lceil \frac{3N}{4}\rceil$ of the mirrors, and that the first $\lceil \frac{3N}{4}\rceil$ of these mirrors are all distinct? The laser is considered to hit the mirror it starts from.

Note: $\lceil x\rceil$ represents the smallest integer greater than or equal to $x$.

Constraints

For this problem, you will NOT be required to pass ANY of the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

$2\le N\le 100000$
$1\le x_i,y_i\le {10}^6$
$|A_i|,|B_i|\le 2\cdot {10}^{12}$

It is guaranteed that $x_i$ and $y_i$ are generated uniformly at random and that all mirror locations are distinct. Note that $A_i$ and $B_i$ are not necessarily generated uniformly at random.

Subtask 1 [10%]

$2\le N\le 4$

Subtask 2 [10%]

$2\le N\le 400$

Subtask 3 [20%]

$2\le N\le 10000$

Subtask 4 [60%]

No additional constraints.

Input Specification

The first line contains a single integer $N$.

The next $N$ lines describe the mirrors. Each line contains $4$ integers, $x_i$, $y_i$, $A_i$, and $B_i$, indicating the $i^{th}$ mirror is located at $(x_i,y_i)$ and has a reflection behaviour described by the integers $A_i$ and $B_i$.

Output Specification

If you cannot fire a laser starting at one of the mirrors in the direction of a different mirror, such that it hits at least $\lceil \frac{3N}{4}\rceil$ of the mirrors, and that the first $\lceil \frac{3N}{4}\rceil$ of these mirrors are all distinct, output -1 and only -1.

Otherwise, output $\lceil \frac{3N}{4}\rceil$ distinct integers on a single line, the $i^{th}$ of which is $Z_i$. This represents the laser being fired from mirror $Z_1$ in the direction of mirror $Z_2$, and will hit all mirrors from $Z_1$ to $Z_{\lceil \frac{3N}{4}\rceil }$ in that order.

Mirrors are $1$-indexed and based on the order of the input.

Note that for this problem, a verdict involving Presentation Error indicates that your output format is incorrect, including, but not limited to not outputting the correct number of distinct integers.

Sample Input 1

4
1 1 -1 0
1 3 -1 0
3 3 -1 0
3 1 -1 0

Sample Output 1

-1

Sample Explanation 1

No matter which direction we fire the laser in, we can only hit at most $2$ mirrors. The mirrors are represented as coloured line segments in the image, however they do not actually take up more than a single point in space.

Sample Input 2

4
1 1 0 -1
1 3 0 1
3 3 0 -1
3 1 0 1

Sample Output 2

2 3 4

Sample Explanation 2

If we fire the laser starting from mirror $2$ in the direction of mirror $3$, the first $3$ mirrors that are hit are $2$, $3$, and $4$, in that order.