Hole in One

Time limit5sMemory limit256 MB

Summary

Find the most walls a ball shot from the origin can destroy by bouncing off axis-aligned walls before dropping into the hole.

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

Problem

Janine went to her local game store and bought Hole in One, a new mini golf game for her computer. As the name says, the goal is to shoot the ball into the hole with a single shot. The game also borrows from brick breaker games: the playing field holds several walls, and a wall is destroyed when the ball hits it. The score of a successful shot depends on how many walls were destroyed, so Janine wants to know the largest number of walls she can hit while still making a hole in one.

Think of the playing field as the cartesian plane with the ball starting at the origin. Each wall is a line segment parallel to the $x$ axis or to the $y$ axis, and the walls do not intersect. The diameter of the ball is negligible, so the ball is a single point.

Figure: an illustration of the first sample input. The ball bounces off two walls, at point 1 and at point 2. By the time it passes point 3, that wall has already vanished.

Two things happen whenever the ball hits a wall.

The direction of the ball changes in the usual way: the angle of incidence equals the angle of reflection.
The wall that the ball touched is destroyed. Following common video game logic, no rubble remains and the place where the wall stood is completely empty.

A wall segment contains both of its endpoints. If the ball touches a wall exactly at an endpoint, that wall is destroyed too and the ball is reflected by the same rule.

Janine also picks the power of the shot. The power decides how far the ball rolls, and the ball may roll over the hole several times and drop in on whichever pass she wants. So the best shot may roll over the hole first, hit more walls, and only later drop into the hole.

Input

The first line contains one integer $n$ ( $0 \le n \le 8$ ), the number of walls.

The second line contains two integers $x$ and $y$ , the coordinates of the hole.

Each of the next $n$ lines contains four integers $x_1$ , $y_1$ , $x_2$ , and $y_2$ , describing a wall with endpoints $(x_1, y_1)$ and $(x_2, y_2)$ . Exactly one of $x_1 = x_2$ and $y_1 = y_2$ holds.

The hole is not at the origin and not on a wall. No two walls touch or intersect. No wall lies completely on the $x$ axis or on the $y$ axis. All coordinates in the input are integers with absolute value at most $1000$ .

Output

If there is no way to shoot the ball so that it reaches the hole, print impossible. Otherwise print the largest number of walls that can be destroyed in a single hole in one shot.

Examples3

Example 1
Input
```
3
4 2
1 1 1 2
2 1 2 2
3 1 3 2
```
Expected output
```
2
```
Example 2
Input
```
1
2 0
1 -1 1 1
```
Expected output
```
impossible
```
Example 3
Input
```
2
-2 4
2 4 2 2
0 6 -2 6
```
Expected output
```
2
```