Mô tả và yêu cầu

Steve được tặng một chiếc bánh ga tô sinh nhật hình chữ nhật kích thước 𝑚 × 𝑛. Steve rất
thích hình vuông và dự định cắt nó ra thành các miếng hình vuông. Để làm được việc đó Steve
tưởng tượng chiếc bánh như một hình chữ nhật góc toạ độ góc trái dưới là (0,0) và toạ độ góc
trên phải là (𝑚, 𝑛).
Đang mãi suy nghĩ nên Steve không nh ận thấy em mình đã nhanh tay thực hiện 𝑘 lần cắt,
mỗi lát cắt song song với cạnh của chiếc bánh và đi suốt toàn bộ bánh. Điều này làm Steve hết
sức buồn rầu chán nản và quyết định chỉ cắt một miếng bánh hình vuông lớn nhất đặt lên bàn.
Yêu cầu: Cho 𝑛, 𝑚, 𝑘 và các lát cắt 𝑡𝑖, 𝑣𝑖, trong đó 𝑡𝑖 = 0 xác định lát cắt 𝑥 = 𝑣𝑖 (0 ≤ 𝑥 ≤
𝑛), 𝑡𝑖 = 1 xác định lát cắt 𝑦 = 𝑣𝑖 (0 ≤ 𝑦 ≤ 𝑚). Hãy xác định độ dài 𝑑 cạnh hình vuông lớn
nhất có thể cắt.

Dữ liệu vào

+ Dòng đầu tiên chứa 3 số nguyên 𝑛, 𝑚, 𝑘 (1 ≤ 𝑛, 𝑚 ≤ 109; 0 ≤ 𝑘 ≤ 105)
+ Dòng thứ 𝑖 trong 𝑘 dòng tiếp theo mỗi dòng chứa 2 số nguyên 𝑡𝑖, 𝑣𝑖

Dữ liệu ra

+ Ghi ra số nguyên 𝑑

Ví dụ

Input       Output
                                            10 10 2      5
                                            1 5
                                            0 3