Maximum Manhattan Distance to Nearest Power Station

You are given a square city grid of side length n along with coordinates of houses and power stations. Each coordinate is given as an integer pair. A house or power station is considered valid only if its coordinates satisfy 0 \le x, y < n.

Your task is to calculate the maximum Manhattan distance from any valid house to its nearest valid power station. The Manhattan distance between two points \((x_1, y_1)\) and \((x_2, y_2)\) is given by the formula: \( |x_1 - x_2| + |y_1 - y_2| \).

Note:

• If n equals 0 or there are no houses, output 0.
• If there are no valid power stations, output -1.

Compute the minimum Manhattan distance for each house among all power stations, and then take the maximum over all these minimum distances.

inputFormat

The first line contains an integer n (the side length of the city grid).

The second line contains an integer h, the number of houses.

The next h lines each contain two integers representing the coordinates of a house.

The following line contains an integer s, the number of power stations.

The next s lines each contain two integers representing the coordinates of a power station.

outputFormat

Output a single integer which is the maximum Manhattan distance from any valid house to its nearest valid power station, or 0 or -1 according to the rules.

The output should be printed to stdout.

## sample

5
3
0 0
0 4
4 0
1
2 2

4