Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P184SUMK - ROUND 4K - Vượt ngục 6

Để trốn thoát khỏi nhà tù Fox River, Michael Scofield phải vượt qua được một vùng đất rộng với rất nhiều chòi canh gác, anh cần tính toán xem khoảng cách gần nhất từ mỗi điểm trên hành trình di chuyển đến các chòi canh gác là bao nhiêu để đánh giá độ nguy hiểm và tính toán thời gian cho hợp lý.

Biết rằng vùng đất có dạng hình chữ nhật song song với trục tọa độ với tọa độ góc dưới trái là (1,1) và tọa độ trên phải là (m,n). Scofield chỉ di chuyển theo hướng song song với cạnh của vùng đất hình chữ nhật và mỗi lần di chuyển được đúng 1 đơn vị khoảng cách. 

Cho tọa độ các chòi canh gác, điểm bắt đầu và điểm kết thúc trên vùng đất, hãy giúp Scofield tính xem khoảng cách lớn nhất có thể từ các điểm trên hành trình của anh so với các chòi canh gác là bao nhiêu.

Input

Dòng đầu tiên gồm 2 số tự nhiên m,n (2 ≤ m,n ≤ 1000) – tọa độ góc trên trái (giới hạn của cánh đồng)

Dòng tiếp theo gồm 4 số tự nhiên xs,ys, xt,yt là tọa độ điểm bắt đầu và tọa độ đích (1 ≤ xs, xt ≤ m, 1 ≤ ys, yt ≤ n).

Dòng tiếp theo là k – số chòi canh gác (k ≤ 106) - k dòng tiếp theo là tọa độ của các chòi gác

Không có 2 chòi nào cùng vị trí, và không có chòi ở điểm bắt đầu và điểm đích. Chỉ quan tâm đến khoảng cách từ các điểm nguyên trên đường đi.

Output

Một số nguyên duy nhất là bình phương “khoảng cách gần nhất đến chòi” lớn nhất có thể từ các điểm đường đi, nếu bắt buộc phải đi qua chòi thì in ra 0.

Example

Input:
5 5
1 1 5 5
2
3 3
4 2

Output:
4
Input:
4 4 
1 1 1 1
3
1 4
4 1
3 3

Output:
8

Giải thích:

Test 1


Được gửi lên bởi:Admin
Ngày:2018-07-27
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.