Helilin has the shape of a line segment with a length of 2 L on a two-dimensional plane.
There are several line-segment-shaped obstacles around the heliline.

Helilin loses strength when it comes in contact with obstacles.
Perfectionist Helilin decides to finish unscathed.

Helilin can do the following:

• Translation
• Rotate exactly 180 / r degrees counterclockwise around the midpoint of the line segment representing heliline

However, the two-dimensional plane has a y-axis in the upward direction.

There are two points S and G around the heliline.
Initially, the center of the heliline is at point S, parallel to the x-axis.

Helilin is good at translating, but not good at rotating.
Your job is to find the minimum number of rotational actions required for Hellin to move the center from point S to point G.
If you can't move it, detect that too.

However, note the following:

• Helilin cannot rotate while moving.
• If the heliline can hit an obstacle while rotating, it cannot rotate.
• Obstacles can intersect each other.
• Treat line segments as having a sufficiently small finite thickness. See the last sample.

Input

The input is given in the following format.

L r
sx sy
gx gy
n
x11 y11 x12 y12
...
xn1 yn1 xn2 yn2

L represents half the length of heliline. r determines the rotation angle. (sx, sy) is the coordinates of the point S, and (gx, gy) is the coordinates of the point G. n represents the number of obstacles. (xi1, yi1) and (xi2, yi2) are the endpoints of the line segment representing the i-th obstacle.

Constraints

The input satisfies the following constraints.

• 1 ≤ n ≤ 30
• 2 ≤ r ≤ 11
• 1 ≤ L ≤ 105
• Absolute value of each component of the coordinates included in the input is 105 or less
• All numbers in the input are integers
• About i = 1, ..., n (xi1, yi1) ≠ (xi2, yi2)
• When the heliline is placed horizontally on the x-axis at the starting point, the distance (line segment to line segment) from the obstacle is greater than 10-3.
• The solution does not change even if the end point of the line segment representing the obstacle is extended or shortened by 10-3 in both directions.
• Increasing or decreasing L by 10-3 does not change the solution
• If the line segment of the obstacle is written as li, there are at most 100 pairs (i, j) such that 1 ≤ i ≤ j ≤ n and the distance between li and lj is 2 L or less.
• The goal point is never on an obstacle

Output

Output the minimum number of rotational actions required to move from the start point to the goal point in one line. If you can't move it, print -1 on one line.

Examples

Input

1 2
3 3
2 -1
4
1 0 1 5
0 1 4 1
0 4 6 4
5 0 5 5

Output

1

Input

1 2
3 3
2 -1
4
1 0 1 5
0 1 6 1
0 4 6 4
5 0 5 5

Output

-1

Input

1 4
3 3
7 0
5
1 0 1 5
0 1 6 1
0 4 6 4
8 0 2 5
6 0 4 2

Output

3

Input

2 2
4 2
4 5
5
1 5 2 0
0 4 3 4
0 1 8 1
7 0 7 5
8 4 5 4

Output

-1

见题面

见题面