Everybody knows that cake comes in two shapes, circular or rectangular.
Everybody except for Wesley.
In his defence:
You wouldn't buy a rectangular shaped pizza would you?
Thus Wesley has only ever cut his cake in one way.
- Imagine a Cartesian grid over the center of the cake labelled at .
- Make cuts over the line formed by within the cake's boundaries.
With Wesley's birthday coming up, his friends have decided to play a little prank on him. They have purchased a square shaped cake with side length and would like to know the side length of the largest axis-aligned square obtainable that does not intersect with any cut. A square intersects a cut if there is a non-zero area of the square on both sides of the cut. This means that touching a cut does not count as an intersection.
Slope will be given as where .
The first line will contain two integers, and , half the length of the cake, and the number of cuts Wesley makes.
The next lines will each contain two integers, , the numerator and denominator of the slope of the line used to determine the cut. and are guaranteed to be coprime, and the pair is guaranteed to be unique.
Output two positive integers, and space-separated on one line. This means the side length of the largest obtainable axis-aligned square is . Note that and must be coprime.
Subtask 1 [30%]
Subtask 2 [70%]
No additional constraints.
Sample Input 1
1 2 -1 1 1 1
Sample Output 1
Explanation For Sample 1
The following image shows the cake:
The red square is the cake, and the blue and green lines show the two cuts. The black line shows one of the many different largest squares obtainable.
Sample Input 2
2 2 -1 2 1 1
Sample Output 2
Sample Input 3
1000 2 -1000 1 1000 1
Sample Output 3