hellokitty

Problem Description

Rar the cat lives in Hello World along with all the other cats, including Tom (from Tom and Jerry), Sylvester and Garfield. Hello World is generalized to become a world in a 2 dimensional Cartesian coordinate system, where each cat within the world lives at a point (X, Y), where X and Y are integers. There are a total of N cats in Hello World that all live in unique locations.

The problem comes when Rar the cat decides to build a community centre for the cats. The community centre will be called 'Hello Kitty' and serves as the main area for fellow felines to interact with each other. Hello Kitty will feature a fishing pool, high-rise trees as well as various services such as claw sharpening and dry cleaning services so that felines can keep their nails as sharp as possible and keep clean without touching a single drop of water.

However ambitious the plan is, Rar the cat does not know where to place the community centre. One particular way is to minimize the sum of distances between all the cat's houses to the point of which he decides to build the community centre at. However, as the cost of building at a more densely populated region is naturally higher, he might not have sufficient funding to build Hello Kitty there. Therefore, he has shortlisted a list of M locations which he intends to build Hello Kitty at. Since its very time consuming and mentally draining to calculate the sum of distances between all the cat's houses to each of the shortlisted points, he wants you to create a program to calculate this sum of distances for him given the list of where N cats live and the list of M locations Hello Kitty is shortlisted to be built at.

For Hello World, the distance between 2 points (from a cat's house to the shortlisted location of Hello World) is the Manhattan Distance between the two points. The Manhattan Distance between two points is simply the sum of differences of the 2 points' X and Y co-ordinates. For example, the Manhattan Distance between (a, b) and (c, d) is abs(a-c) + abs(b-d) or |a - c| + |b - d|, where 'abs' is the absolute function.

Input

The first line of input consist of a single integer, N.

Subsequent N lines will follow with 2 integers per line, X and Y. These N lines denote the X and Y co-ordinates of the N cats' houses living in Hello World. It is guaranteed that there are no 2 lines (within this N lines) that have the same X and Y co-ordinates.

The next line will consist another integer, M.

M lines will follow with 2 integer each, X and Y. However, this time, the lines denote the X and Y co-ordinates of the M shortlisted locations for Hello Kitty.

Output

For each shortlisted co-ordinate for Hello Kitty to be built, output a single number denoting the sum of distances from all the N cats' houses to the location.

However, Rar the Cat can be careless and included the co-ordinates of another cat's house as a possible location of Hello Kitty. In this case, please output 'Cannot build here.' for that line only.

Limits

Subtask 1 (13%): 0 < N, M ≤ 1000, 0 ≤ X, Y ≤ 1000

Subtask 2 (18%): 0 < N, M ≤ 100000, 0 ≤ X, Y ≤ 5000

Subtask 3 (20%): 0 < N, M ≤ 100000, 0 ≤ X, Y ≤ 1000000

Subtask 4 (49%): 0 < N, M ≤ 100000, 0 ≤ X, Y ≤ 2000000000

Subtask 5 (0%): As per sample testcases

Sample Testcase 1

Input:

5
0 1
1 3
0 7
3 8
2 3
10
0 0
0 1
0 2
2 8
3 7
2 4
3 5
8 3
1 1
1 2

28
Cannot build here.
20
24
24
18
22
45
22
19

Sample Testcase 2

Input:

5
0 0
0 1
0 2
1 0
2 0
10
0 0
0 1
0 2
2 8
3 7
2 4
3 5
8 3
1 1
1 2

Cannot build here.
Cannot build here.
Cannot build here.
44
44
24
34
49
8
11