It is the time for the Holidays, which means it’s time for the annual Holiday Cookie Throwing contest where cookies are thrown against a wall. Cookies are really simple polygons that rotate clockwise while in flight.

Due to many years of advanced research and precise throwing equipment, these cookies can fly under idealized conditions: their center of mass follows an ideal parabola ($g = 9.81 \frac{m}{s^2}$), and their angular velocity stays constant.

Given a cookie’s shape, initial angle and speed as well as its angular velocity, compute which of the cookie’s corners hits the wall first, and when!

-----Input-----
The input consists of a single test case. The first line contains $5$ numbers: an integer $n$ ($3 \le n \le 20$) denoting the number of vertices of the cookie polygon, a real number $\omega $ ($0 \le \omega \le 10$), the angular velocity in $\text {rad}/s$ in clockwise direction, a real number $v_0$ ($1 \le v_0 \le 10$), the initial velocity of the cookie in $\frac{m}{s}$, an integer $\theta $ ($0 \le \theta \le 80$), the initial angle of the cookie’s trajectory, given in degrees measured counter-clockwise relative to the $(1, 0)$ unit vector, a real number $w$ ($20 \le w \le 500$), denoting the $x$-coordinate of the wall towards which the cookie is moving. You may assume that there are no other objects in space aside from the cookie, and that the wall is of infinite height (e.g., from $-\infty \ldots \infty $).

This is followed by $n$ lines, one for each vertex. Each line contains two real numbers $x_ i$ and $y_ i$ ($|x_ i| < 20, |y_ i| < 20$) denoting the initial position of a cookie’s corner. Corners are numbered $1 \ldots n$. The cookie polygon’s vertices are given in counter-clockwise order. The polygon is simple (e.g., not self-intersecting) and has a non-zero area.

All real numbers are given with no more than $6$ decimal digits after the period.

-----Output-----
Output two numbers $i$ and $T_ i$, denoting the index $i$ ($1 \le i \le n$) of the corner that hits the wall first and the time $T_ i$ in seconds when that happens. The index corresponds to the order in the input. $T_ i$ must be given with an absolute error of less than $10^{-3}$! You may assume that no two vertices hit the wall within $10^{-2}$ seconds of each other, and that the first vertex to hit the wall would pierce it for at least $10^{-3}$ seconds.

-----Examples-----
Sample Input 1:
3 6 5 45 20
0 0
2 0
1 1.5
Sample Output 1:
2 5.086781

Sample Input 2:
3 0.25 2 45 20
0 0
2 0
1 1.5
Sample Output 2:
1 12.715255

Source: kattis | Difficulty: HARD


Solutions: