Description

A scourge of frogs destroying all the crops has started in Byteotia. A farmer named Byteasar has decided to fight the vermin with peculiar “scarefrogs” that he has set up at certain points of his field. While moving from one place to another, every frog tries to keep as far from them as possible, i.e., it maximizes the distance to the closest scarefrog.

Byteasar’s field is rectangular. The frogs leap in directions parallel to the field’s sides, and each leap has unit length 1. For a given route, the scarefrog-distance is the minimum, over all points visited continuously along the route (including the points between leaps), of the distance to the nearest scarefrog.

Byteasar already knows the most common starting and destination points of the frogs’ routes, so he experiments with various deployments of scarefrogs. He asks you to compute the maximum (over all routes from the start to the target) scarefrog-distance achievable while still reaching the target. We call this value the frogshold distance. You should output the square of this number.

In other words, given a grid with some “bad” points (the scarefrogs), find a path from the start to the end that maximizes the minimum distance, over all points on the path, to the nearest bad point, and output this maximum squared.

Input Format

• The first line contains two integers $w_x$ and $w_y$ — the width and height of the field ($2 \le w_x, w_y \le 1000$).
• The second line contains four integers $p_x$, $p_y$, $k_x$ and $k_y$; $(p_x, p_y)$ is the frog’s start position, and $(k_x, k_y)$ is the target position ($1 \le p_x, k_x \le w_x$, $1 \le p_y, k_y \le w_y$).
• The third line contains one integer $n$ ($1 \le n \le w_x \cdot w_y$).
• Each of the next $n$ lines contains two integers $x_i$ and $y_i$ — the coordinates of the $i$-th scarefrog.
• No two scarefrogs occupy the same position, and none of them is at $(p_x, p_y)$ or $(k_x, k_y)$.

Output Format

Output a single integer — the square of the frogshold distance. If the frog cannot avoid leaping directly onto some scarefrog, output $0$.

5 5
1 1 5 5
2
3 3
4 2

4

Hint

Translated by ChatGPT 5