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 **

#### Input Specifications

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 Specifications

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**.

#### Subtasks

##### Subtask 1 [30%]

##### Subtask 2 [70%]

No further constraints.

#### Sample Input 1

```
1 2
-1 1
1 1
```

#### Sample Output 1

`2 3`

#### Explanation For Sample 1

The following image shows the cake:

The red square is the cake, and the blue and green lines shows 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

`3 2`

#### Sample Input 3

```
1000 2
-1000 1
1000 1
```

#### Sample Output 3

`2000000 2001`

## Comments