Archaeological Digs

Time limit1sMemory limit128 MB

Summary
Given repeated item coordinates on a small grid and a list of query cells, sum how many items fall in those cells.
Level

Easy3 of 10

Topics
Hash map, Implementation
Solved
No attempts yet

Problem

Archaeologists at a dig divide the area they are examining into a grid and record which grid cell each item is found in. This makes it easy to tell how many items were found in a given cell.

For each scenario you are given the coordinates of the cells where items were found. For a list of query cells, determine the total number of items contained in those cells.

Input

The input consists of several scenarios.

The first line of each scenario contains two integers XX and YY, separated by a space, representing the length and width of the grid (0<X,Y≤1000 < X, Y \le 100). A scenario in which XX and YY are both 00 marks the end of input.

The second line contains a single integer MM, the number of items located by the archaeologists (0<M≤100000 < M \le 10000). This is followed by MM lines, each containing the XX and YY coordinates of the cell in which an item was found. The grid coordinate system starts at 0,00, 0, and several items may be found in a single cell, so cell coordinates may be repeated.

After the MM item locations comes a list of cells for which the total number of found items is required. The first line of this section is a single integer NN, the number of cells (0<N≤X×Y0 < N \le X \times Y). It is followed by NN lines, each containing the XX and YY coordinates of a cell.

Output

Output a single line for each scenario. Each line contains the total number of items found in the NN listed cells.

Hint

In the example, cell (9,9)(9, 9) contains 22 items (it appears twice in the input list), cell (4,5)(4, 5) contains 11, and cell (6,3)(6, 3) contains none (it does not occur in the input list). The total is therefore 2+1+0=32 + 1 + 0 = 3.

Examples1

  1. Example 1

    Input
    10 10
    8
    4 5
    3 4
    0 0
    1 5
    9 9
    5 6
    3 4
    9 9
    3
    9 9
    4 5
    6 3
    0 0
    
    Expected output
    3