Sân thi đấu

Sàn một nhà thi đấu là một hình chữ nhật kích thước ~m \times n~ được chia thành lưới ô vuông đơn vị, các hàng được đánh số từ ~1~ đến ~m~ từ trên xuống dưới và các cột được đánh số từ ~1~ đến ~n~ từ trái qua phải, ô nằm trên giao của hàng ~i~ và cột ~j~ được gọi là ô ~(i, j)~. Khi mới được xây dựng, tất cả các ô là ô trống và được coi là có độ cao bằng ~0~.

Trong quá trình sử dụng, nhà thi đấu đã tổ chức ~k~ sự kiện thể thao đánh số từ ~1~ tới ~k~. Ở sự kiện thứ ~p~ ~(p = 1, \ldots, k)~, người ta trải thêm các tấm nệm vào tất cả các ô thuộc hình chữ nhật có góc trái trên là ~(x_p, y_p)~ và góc phải dưới là ~(u_p, v_p)~, làm tăng độ cao của những ô này lên ~1~ đơn vị. Tức là bao gồm tất cả các ô ~(i, j)~ có ~x_p \le i \le u_p~ và ~y_p \le j \le v_p~.

Sắp tới có cuộc thi trượt Patin tại nhà thi đấu. Vì các tấm nệm mềm không thích hợp cho môn thể thao này, ban tổ chức muốn chọn một hình vuông có các cạnh song song với các cạnh sàn nhà và toàn bộ các ô bên trong hình vuông đó đều cao bằng nhau để đặt lên đó một tấm phủ cứng làm sân trượt Patin.

Yêu cầu

Tìm cạnh hình vuông lớn nhất mà ban tổ chức có thể sử dụng như mô tả trên.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên dương ~m, n, k~ ~(m, n \le 2000; k \le 10^5)~.
• Dòng thứ ~p~ trong ~k~ dòng tiếp theo ghi bốn số nguyên ~x_p, y_p, u_p, v_p~ ~(x_p \le u_p \le m; y_p \le v_p \le n)~, với mọi ~p = 1, \ldots, k~.

Kết quả

Ghi ra một số nguyên duy nhất là độ dài cạnh hình vuông tìm được.

Ví dụ

Dữ liệu vào

6 6 4
2 2 3 6
2 2 6 3
2 4 4 5
4 2 6 4

Kết quả

3

Ràng buộc

• Có ~40\%~ số điểm có ~m, n, k \le 200~.
• Có ~30\%~ số điểm tiếp theo có ~m, n \le 200~.
• Có ~30\%~ số điểm còn lại không có ràng buộc gì thêm.