Mirrors

Farmer John's cows have been causing too much trouble around the farm, so FJ wants to keep a closer eye on them. By installing $N$ reflective fences ($1 \le N \le 200$) at various spots on the farm, he hopes to be able to see from his house at $(0,0)$ to the barn at $(a,b)$.

On a 2D map of the farm, fence $i$ is a short line segment centered at the integer location $(x_i, y_i)$ and tilted 45 degrees (either like / or like \). For example, a fence oriented like / at position $(3,5)$ could be described as the line segment from $(2.9, 4.9)$ to $(3.1, 5.1)$. Every fence (and the barn) lies at a distinct position with integer coordinates in the range $-10^6 \dots 10^6$. No fence lies at $(0,0)$ or $(a,b)$.

FJ sits at his house $(0,0)$ and looks directly to the right (the $+x$ direction). With his gaze bouncing off some of the reflective fences, he hopes to see the point $(a,b)$. Unfortunately, FJ thinks he oriented one of his fences incorrectly (for example \ instead of /). Output the index of the first fence in FJ's list such that toggling its direction (between / and \) lets FJ see the point $(a,b)$.

If FJ can already see $(a,b)$ without toggling any fence, output $0$. If he still cannot see $(a,b)$ even after toggling a single fence, output $-1$.

• Line 1: Three space-separated integers $N$, $a$, and $b$.
• Lines 2 through $N+1$: Line $i+1$ describes fence $i$ in the form x_i y_i / or x_i y_i \, where $(x_i, y_i)$ is the center of the fence and / or \ gives its orientation.

• Line 1: The index of the first fence whose toggling lets FJ see $(a,b)$. Output $0$ if FJ can already see $(a,b)$, or $-1$ if there is no way to see $(a,b)$ even after toggling one fence.

Input Details

A map of the farm looks like this (H is FJ's house, B is the barn).

3 .\.....
2 //.\..B
1 .......
0 H../...
  0123456

Output Details

By toggling the fence at position $(3,2)$, FJ can see the barn. On the map:

3 .\.....
2 //./--B
1 ...|...
0 H--/...
  0123456