Avoiding the Smell

As the world camp continues, more people have started to smell because they have not washed. When you need to move from a starting point to a destination inside a classroom, you want to choose a path that stays as far as possible from the seats occupied by smelly people.

The classroom is represented as a rectangular grid of integer coordinates. Let Wx and Wy be the width and height of the classroom. Each smelly person's position (x, y), the starting point (sx, sy), and the destination (tx, ty) satisfy the following conditions.

• 1 <= x, sx, tx <= Wx
• 1 <= y, sy, ty <= Wy
• 2 <= Wx, Wy <= 1,000
• The number n of smelly people satisfies 1 <= n <= Wx * Wy - 2.

In one move, you may move by 1 in a horizontal or vertical direction. During the movement, you must always remain at positive integer coordinates inside the classroom. The set of integer grid points visited while moving from the start to the destination is called a path.

The distance between a path and the smelly people is the minimum Euclidean distance over every choice of one point on the path and one point occupied by a smelly person. An optimal path is a path that maximizes this minimum distance among all possible paths.

Given the start, the destination, and the positions of the smelly people, find the square of the distance between an optimal path and the smelly people.

The first line contains two integers Wx and Wy, the size of the classroom.

The second line contains four integers sx, sy, tx, ty, the coordinates of the start and destination.

The third line contains the integer n, the number of smelly people.

Each of the next n lines contains two integers xi and yi, the coordinates of one smelly person. No smelly person is seated at the start or at the destination.

Print, on the first line, the square of the distance between the smelly people and an optimal path. If every possible path must pass through a position occupied by a smelly person, print 0.