Big Square Piece

Interview

Time limit2sMemory limit1024 MB

Summary

Given an n by m cake and k cuts parallel to its sides, find the side of the largest square that fits in one resulting piece.

Level: Easy3 of 10
Topics: Sorting, Implementation
Solved: No attempts yet

Statement

Petya received a rectangular cake with sides n and m as a birthday present. He likes rectangles, but he likes squares even more, so he wanted to cut the cake into many identical square pieces.

Unfortunately, his younger brother Lesha got to the cake first and made several cuts parallel to the sides. Petya was upset. Lesha wants to cheer him up by cutting the largest possible square out of one of the resulting pieces. First he needs to know the side of the largest square that can be cut from the pieces. Help Lesha.

Input

The first line contains three integers n, m and k (1 ≤ n, m ≤ 10^9, 0 ≤ k ≤ 10^5). The next k lines describe the cuts. Each cut is given by two numbers t and v. Place a coordinate system so that one corner of the cake is at (0, 0) and the opposite corner is at (n, m). Then t = 0 means a cut along the line x = v (0 ≤ x ≤ n), and t = 1 means a cut along the line y = v (0 ≤ y ≤ m).

Output

Print a single number: the side of the largest square that can be cut from the pieces obtained after cutting the cake.

Examples2

Example 1
Input
```
10 10 2
1 5
0 3
```
Expected output
```
5
```
Example 2
Input
```
4 7 0
```
Expected output
```
4
```