Description

Having once invented the Super Particle Cannon · Modified, the inventor SHTSC has now unveiled his new invention: the Laser Generator — a mysterious device that can produce high-energy lasers.

From a top-down view, the Laser Generator is an infinite plane containing one directional laser emitter and several laser deflection devices. An example is shown in the figure: the thin arrow denotes the directional laser emitter, and the thick segments denote the laser deflection devices.

The laser emitted by the directional emitter can be regarded as a ray. When it encounters a deflection device, it will be deflected. Interestingly, the deflection devices used by SHTSC do not obey the law of reflection like traditional mirrors. For each deflection device, there is a fixed deflection coefficient $λ$, and the relation between the exit angle $β$ and the incident angle $α$ is $β=λα$. The device can also amplify the laser’s energy in the process.

Notes:

1. The incident angle is the angle between the incident ray and the normal vector of the deflection plane.
2. Both sides of a deflection device can deflect.
3. If the laser is incident parallel to a deflection device, we consider that no deflection occurs.
4. If it is not parallel and hits an endpoint, we consider that a deflection occurs.
5. When $β>\frac{1}{2}π$, it may be deflected to the other side.

Now SHTSC hopes you will simulate the operation of his Laser Generator to help compute which deflection devices the laser is deflected by.

Input Format

The first line contains four integers $x, y, dx, dy$, indicating that the directional laser emitter is at $(x, y)$ and points in direction $(dx, dy)$.

The second line contains an integer $n$, the number of laser deflection devices. The next $n$ lines each contain six integers $x1, y1, x2, y2, a, b$, describing one deflection device as the segment from $(x1, y1)$ to $(x2, y2)$ with deflection coefficient $\lambda=a/b$.

Output Format

Output one line with a sequence of integers separated by spaces, indicating the indices of the deflection devices the laser hits in order (devices are numbered from $1$ to $n$ in input order). If the laser is deflected more than $10$ times, output only the indices of the first $10$ devices hit. In particular, if the laser is not deflected by any device, output NONE.

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

1 2

Hint

Sample Explanation

As shown in the figure, the laser is deflected by device $1$ and then device $2$ in order.

Constraints

• For $10\%$ of the testdata, $n=1$.
• For $40\%$ of the testdata, $a=b=1$.
• For $100\%$ of the testdata, $n \le 100$; the absolute values of all coordinates and of $a$ and $b$ do not exceed $1000$; $a$ and $b$ are nonzero; $dx$ and $dy$ are not both zero. It is guaranteed that no two deflection devices intersect, and the starting point of the laser emitter is not on any deflection device.

Translated by ChatGPT 5