-97. Bicycle and Parking Lot

Task Description

National Taiwan University wants to enforce bicycle parking regulations by moving illegally parked bicycles to remote parking lots. There are $n$ parking lots for these illegally parked bicycles. The $i$-th parking lot is located at $(x_i, y_i)$ and has a capacity of $c_i$ bicycles. The university moves an illegally parked bicycle to the nearest parking lot. The distance between a bicycle and a parking lot is the sum of their absolute value in $x$ and $y$ coordinates. For example, the distance between $(1, 3)$ and $(-2, 2)$ is $3 + 1 = 4$. If there are two nearest parking lots, we choose the one with a smaller $x$ coordinate. If the $x$ coordinates are the same, we choose the one with a smaller $y$ coordinate. If all nearest parking lots are full, that is, already have their capacity of bicycles, we move the bicycle to one of the second nearest parking lots, and so on. We assume that the total capacity of all parking lots is sufficient for all illegally parked bicycles. Given the locations and capacity of all parking lots, please determine the parking lots a sequence of illegally parked bicycles will go to.

Input

The first line of the input is the number of parking lots $n$. Each of the following $n$ lines has the $x$, $y$ coordinate, and the capacity of a parking lot. The next line has an integer $m$, the number of illegally parked bicycles. Each of the next $m$ lines has the $x$ and $y$ coordinates of the bicycle. We move the bicycles according to the order in the input.

Output

The output has $n$ lines. The $i$-th line is the number of bicycles in the $i$-th parking lots after moving all $m$ bicycles to the parking lots.

Bounds

• $n$ is positive and no more than 10.
• $m$ is positive and no more than 100000.
• The $x$ and $y$ coordinates are all between -10000 and 10000.

Sample input

2
1 1 1
100 100 100
3
0 0
2 2
3 3

Sample output

1
2