Canadian Computing Competition: 2009 Stage 2, Day 1, Problem 1

Oh no! You are under attack by a swarm of boxes. The $N$ ($0\le N\le 1000$) boxes are all rectangular with sides perpendicular to the axes. To help you defend against these menacing boxes, you have a giant laser at your disposal.

The laser is located at the origin and shoots a single beam in some fixed specified direction. The beam, upon encountering a box, will destroy and reflect off of that box.

Beams are reflected so that if its first intersection point with a box is a horizontal segment of a box, the vertical component of the beam's direction is reversed. Similarly, the horizontal component is reversed when the beam hits a vertical segment. If the beam reflects off a corner of a box, both the horizontal and vertical components of its direction are reversed.

Output the indices of the destroyed boxes in the order that they are destroyed. It is guaranteed that no two boxes will have a common point and that no box contains the origin in its interior or boundary.

Input Specification

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

The second line contains two integers $d_x$ and $d_y$ ($-1000\le d_x,d_y\le 1000$, not both zero), giving the direction in which the laser is pointed so that an unhindered beam fired from the origin will pass through $(d_x,d_y)$.

The next $N$ lines each contain 4 integers: $x_i$, $y_i$, $w_i$ and $h_i$ (where $-1000\le x_i,y_i\le 1000$ and $1\le w_i,h_i\le 1000$) giving the description of the $i^{\text{th}}$ box which has lower left corner $(x_i,y_i)$ and upper right corner $(x_i+w_i,y_i+h_i)$.

Output Specification

Suppose there are $k$ ($k\ge 0$) boxes that are destroyed. The output contains one number per line, with the $i^{\text{th}}$ line ($i\le k$) containing the index of the box destroyed on the $i^{\text{th}}$ bounce. Notice that there is no output if $k=0$.

Sample Input

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

Description of Sample Input

Three boxes: box 1 covering $(1,0)$ to $(91,20)$, box 2 covering $(1,-22)$ to $(91,-2)$ and box 3 covering $(1,-44)$ to $(91,-24)$. The laser points south-east.

Output for Sample Input

2
1
3

Description of Output for Sample Input

The beam bounces off the middle one (box 2), then into the top one (box 1) and finally destroys the bottom one (box 3).