Billiard

Time limit8sMemory limit256 MB

Summary

Predict which stationary ball a struck billiard ball hits first as it reflects off cushions over a path of length 10000.

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

Problem

A billiard table has a rectangular playing area with no pockets. A cushion runs along all four sides.

You built an ultra precise billiard robot. You put several balls on the table and the robot strikes one of them. The struck ball stops the moment its total travelled distance reaches $10000$ .

When the ball touches a cushion, it turns like a reflection in a mirror. When it touches a corner, it goes back along the path it came from.

Every ball has radius $r$ . Two balls collide when the distance between their centres is $2r$ , and the struck ball reflects off a cushion when the distance from its centre to that cushion is $r$ . The other balls stay where they started until the struck ball reaches one of them.

Predict which ball the struck ball collides with first.

Input

The input is a sequence of datasets. The number of datasets is less than $100$ . Each dataset has the following format.

n
w h r vx vy
x1 y1
...
xn yn

The first line holds the number of balls on the table, $n$ ( $2 \le n \le 11$ ). The next line holds five integers $w$ , $h$ , $r$ , $v_x$ , $v_y$ separated by single spaces. $w$ and $h$ are the width and the length of the playing area ( $4 \le w, h \le 1000$ ), and $r$ is the radius of the balls ( $1 \le r \le 100$ ). The robot strikes the ball in the direction of the vector $(v_x, v_y)$ ( $-10000 \le v_x, v_y \le 10000$ , $(v_x, v_y) \ne (0, 0)$ ).

The next $n$ lines give the positions of the balls. Each line holds two integers separated by a single space, and $(x_i, y_i)$ is the centre of the $i$ th ball in the initial state ( $r < x_i < w - r$ , $r < y_i < h - r$ ). $(0, 0)$ is the north west corner of the playing area and $(w, h)$ is the south east corner. In the initial state no ball touches another ball or a cushion.

The robot always strikes the first ball in the list. The given values carry no error.

The end of the input is a line holding a single $0$ .

Output

For each dataset, print on its own line the number of the ball that first collides with the ball the robot struck. Balls are numbered from $1$ in the order they appear in the input, so the struck ball is ball $1$ . If the struck ball collides with no ball before it stops, print -1.

No two balls collide with the struck ball first at the same time. Changing $r$ by less than $10^{-9}$ changes neither the ball that is hit first nor the way that collision happens.

Examples2

Example 1

Input

3
26 16 1 8 4
10 6
9 2
9 10
3
71 363 4 8 0
52 238
25 33
59 288
0

Expected output

3
-1

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