Thành phố Vô Tận được chia thành những ô vuông đơn vị bởi vô số con đường hai chiều chạy theo hướng nam–bắc và tây–đông. Một đường nam–bắc được đánh số \(0\); số đường tăng dần về phía đông và giảm dần về phía tây. Tương tự, một đường tây–đông được đánh số \(0\); số đường tăng dần về phía bắc và giảm dần về phía nam.

Mỗi giao lộ được biểu diễn bằng cặp số có thứ tự của hai con đường đi qua nó, trong đó số thứ nhất là số của đường nam–bắc. Một số đoạn đường quan trọng hơn được gọi là đường chính.

Một hôm, cảnh sát trưởng Wolf, người bảo vệ nghiêm khắc nhất thành phố, đang tuần tra thì phát hiện tại giao lộ \((A,B)\) một chiếc xe chở vài thành viên của băng BEAR khét tiếng. Wolf nghe nói chúng định đột nhập Kho Mật Ong của thành phố nằm gần giao lộ \((0,0)\), nên quyết định ngăn chặn chúng.

Tuy nhiên, chúng chưa phạm tội nên Wolf không thể bắt giữ. Ông có quyền dừng xe tại một giao lộ và chặn đúng một trong bốn đoạn đường đơn vị tiếp giáp giao lộ đó, nhưng không được chặn đoạn thuộc đường chính.

Wolf quyết định đuổi theo băng BEAR. Ngay trước khi xe của chúng tới một giao lộ, ông có thể vượt lên và chặn một trong bốn đoạn đường đơn vị tại đó. Băng BEAR vẫn có thể đi vào giao lộ, nhưng không thể rời giao lộ theo đoạn bị xe cảnh sát chặn.

Wolf muốn giữ băng BEAR cách Kho Mật Ong càng xa càng tốt. Hãy tìm giá trị lớn nhất \(D\) mà ông có thể bảo đảm sao cho mọi giao lộ \((x,y)\) băng BEAR có thể tới đều thỏa mãn

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(A\) và \(B\), là vị trí ban đầu của băng BEAR. Dòng thứ hai chứa số nguyên \(N\), là số đoạn đường chính. Mỗi dòng trong \(N\) dòng tiếp theo chứa bốn số nguyên \(X_1,Y_1,X_2,Y_2\), cho biết đoạn đường nối \((X_1,Y_1)\) với \((X_2,Y_2)\) là đường chính. Mỗi đoạn đều có \(X_1=X_2\) hoặc \(Y_1=Y_2\).

Dữ liệu ra

In một số nguyên là giá trị lớn nhất của \(D\).

Ràng buộc

• \(|A|,|B| \le 10^6\).
• \(0 \le N \le 500\).
• \(|X_i|,|Y_i| \le 10^6\) với \(i \in \{1,2\}\).

Ví dụ

3 3
3
1 0 3 0
0 0 0 3
3 0 3 1

1