The inventor SHTSC, who once invented the "Super Particle Cannon: Modified," has unveiled his new invention: the Laser Generator—a mysterious device capable of producing high-energy lasers.

When viewed from directly above, the laser generator is an infinite plane containing a directional laser emitter and several laser deflection devices. An example of a laser generator is shown in the figure below, where the thin arrow represents the directional laser emitter and the thick line segments represent the laser deflection devices.

Figure 1: A laser generator

The laser emitted by the directional laser emitter can be treated as a ray. If it encounters a laser deflection device, it will be deflected. Curiously, the laser deflection devices used by SHTSC do not follow the law of reflection like traditional mirrors. Instead, for each deflection device, there is a fixed deflection coefficient $\lambda$, and the relationship between the exit angle $\beta$ and the incident angle $\alpha$ is $\beta = \lambda \alpha$. This process also enhances the energy of the laser. (The incident angle is the angle between the incident ray and the normal vector of the reflecting plane.)

Note: 1. Both sides of a deflection device can deflect the laser. 2. If the laser is incident parallel to the deflection device, it is considered not to be deflected. 3. If the laser is not parallel and hits an endpoint, it is considered to be deflected. 4. The laser may be deflected to the other side.

Figure 2: Laser deflection device

SHTSC now wants you to simulate the operation of his designed laser generator to help him calculate which laser deflection devices the laser is deflected by.

Input

The first line contains four integers $x, y, dx, dy$. These represent the position $(x, y)$ and the direction $(dx, dy)$ of the directional laser emitter.

The second line contains an integer $n$, representing the total number of laser deflection devices.

The following $n$ lines each contain five integers $x_1, y_1, x_2, y_2, a, b$, representing a laser deflection device as a line segment from $(x_1, y_1)$ to $(x_2, y_2)$ with a deflection coefficient $\lambda = a/b$.

Output

Output a single line containing several space-separated integers, representing the indices of the laser deflection devices that the laser hits in sequence (numbered from $1$ to $n$ in the order of input). If the laser is deflected more than $10$ times, only output the indices of the first $10$ deflection devices hit. Specifically, if the laser is not deflected by any deflection device, output NONE.

Examples

Input 1

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

Output 1

1 2

Input 2

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

Output 2

2 1 2 1 2 1 2 1 2 1

Input 3

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

Output 3

NONE

Note

Example 1, Example 2, Example 3

Constraints

For 20% of the data: The laser is deflected at most 1 time.

For an additional 20% of the data: All $a=b=1$.

For 100% of the data: $n \le 100$, all coordinates and the absolute values of $a$ and $b$ do not exceed $1000$, and $a, b \neq 0$. It is guaranteed that all deflection devices do not intersect. The starting point of the laser is not on any deflection device. The direction vector is not a zero vector.