题目描述

仓鼠瓦列拉活动的场地是一张有 $w\times h$ 个节点的矩形网格。一些节点上坐着饥饿的狐狸，它们很想把仓鼠当作美餐。

瓦列拉从节点 $(x_1,y_1)$ 出发，需要到达节点 $(x_2,y_2)$。他只能在上下左右相邻的节点之间移动。

为了活下来，瓦列拉必须尽可能谨慎地规划路线。定义一条路线的谨慎程度为：对于路线经过的每个节点，计算它到最近狐狸的欧几里得距离，再取这些距离中的最小值。节点 $(x_1,y_1)$ 和 $(x_2,y_2)$ 之间的欧几里得距离为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。

请找出谨慎程度尽可能大的路线，输出其最大谨慎程度的平方。

输入格式

第一行包含两个整数 $w,h$，分别表示场地的宽度和高度，满足 $2\le w,h\le1500$。

第二行包含四个用空格分隔的整数 $x_1,y_1,x_2,y_2$，分别表示起点和终点的坐标，满足 $1\le x_1,x_2\le w$，$1\le y_1,y_2\le h$。

第三行包含一个整数 $n$，表示狐狸的数量，满足 $1\le n\le\min(w\cdot h,10^6)$。

接下来 $n$ 行，每行包含两个用空格分隔的整数 $x_i,y_i$，表示第 $i$ 只狐狸所在节点的坐标，其中 $1\le x_i\le w$，$1\le y_i\le h$。

保证所有狐狸所在的节点互不相同，且起点和终点均没有狐狸。

输出格式

输出一个整数，表示瓦列拉可选择的路线的最大谨慎程度的平方。如果每一条从起点到终点的路线都会经过有狐狸的节点，则输出 $0$。

6 6
1 1 6 6
2
1 3
4 1

2

提示

下图展示了瓦列拉在样例中选择的路线。