97. Bicycle and Parking Lot

I'm a slow walker, but I never walk backwards.

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. An illegally parked bicycle will be moved 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 lot, then we choose the one with smaller $x$ coordinate. If the $x$ coordinates are the same, then we choose the the one with smaller $y$ coordinate. If all nearest parking lots are full, that is, have already their capacity of bicycles, the bicycle will be moved to one of the second nearest parking lots, and so on. It is guaranteed that the capacity of all parking lots is sufficient for all illegally parked bicycles. Now given the locations and capacity of all parking lots, please determine which parking lots a sequence of illegally parked bicycles will be moved to.


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 the next line has an integer $m$, the number of illegally parked bicycles. Each of the next $m$ line has the $x$ and $y$ coordinates of the bicycle. The bicycles will be moved according to the order in the input.


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


  • $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

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

Sample output