After Tianyi ate some food, she decided to bury the evidence she had eaten. Because she's afraid that Zhengling will know it.
First, the square is a big hole that the acreage is N * N. At each step, Tianyi will choose a coordinate to bury.
Then Tianyi will ask you that during step X to step Y, the sum of maximum independent holes area.

For example:
The big hole is 3 * 3. Step 1 buries (2, 2), so the maximum independent hole area is 8. Step 2 buries (2, 1), so the maximum independent hole area is 7. Step 3 buries (2, 3), so the maximum independent hole area is 3.
That is, from step 1 to step 3, the sum of independent hole is (8 + 7 + 3) = 18.

This problem contains several cases.
The first line of each case is an integer N (0 < N <= 500), indicates the length of side.
Then follows N * N lines, each line is a coordinate. From (1, 1) to (N, N). You can assume that one coordinate will at most appear once.
Next line follows an integer Q (0 < Q <= 10000), indicates the count of queries.
Next Q lines indicate Q queries.

For each query, you should output the sum of independent holes.