Invasion of the Boxes

Time limit1sMemory limit128 MB

Summary

Simulate a laser ray from the origin that destroys axis-aligned boxes and reflects off them, printing the order of destruction.

Level: Medium6 of 10
Topics: Geometry, Simulation, Implementation
Solved: No attempts yet

Problem

You are under attack by a swarm of boxes. There are $N$ ( $0 \le N \le 1000$ ) boxes, and every box is an axis-aligned rectangle (its sides are parallel to the coordinate axes). To defend yourself, you have a giant laser.

The laser sits at the origin and fires a single beam in one fixed direction. When the beam meets a box, it destroys that box and reflects off it.

The reflection rule depends on where the beam first touches the box:

If the first intersection point lies on a horizontal side of the box, the vertical component of the beam's direction is reversed.
If the first intersection point lies on a vertical side of the box, the horizontal component is reversed.
If the beam first strikes a corner of the box (where a horizontal side and a vertical side meet), both components are reversed.

A destroyed box disappears, so the beam may afterwards travel freely through the region that box used to occupy.

Report the indices of the destroyed boxes in the order in which they are destroyed.

It is guaranteed that no two boxes share any common point, and that no box contains the origin in its interior or on its boundary.

Input

The first line contains $N$ , the number of boxes.

The second line contains two integers $dx$ and $dy$ ( $-1000 \le dx, dy \le 1000$ , not both zero): a beam fired from the origin with nothing in its way passes through the point $(dx, dy)$ .

Each of the next $N$ lines contains four integers $x_i$ , $y_i$ , $w_i$ , and $h_i$ ( $-1000 \le x_i, y_i \le 1000$ and $1 \le w_i, h_i \le 1000$ ) describing the $i$ -th box, whose lower-left corner is $(x_i, y_i)$ and whose upper-right corner is $(x_i + w_i, y_i + h_i)$ . The boxes are numbered $1$ through $N$ in the order given.

Output

Let $k$ ( $k \ge 0$ ) be the number of boxes that are destroyed. Print $k$ lines; the $i$ -th line contains the index of the box destroyed on the $i$ -th bounce. If $k = 0$ , print nothing.

Examples5

Example 1

Input

3
1 -1
1 0 90 20
1 -22 90 20
1 -44 90 20

Expected output

2
1
3

Example 2
Input
```
1
1 0
10 -3 5 6
```
Expected output
```
1
```
Example 3
Input
```
1
0 1
-5 10 10 8
```
Expected output
```
1
```
Example 4
Input
```
1
1 1
10 10 10 10
```
Expected output
```
1
```

Example 5

Input

4
1 1
8 10 10 10
19 -10 10 10
26 10 14 10
36 -10 14 10

Expected output