BOMB2  Bombing
It's a cruel war which kills millions of people and series of cities were ruined. In order to stop it, let's bomb the opponent's base.
It seems to be not a hard work in circumstances of street battles, however, you'll be encountered a much more difficult instance: recounting exploits of the military. In the bombing action, the commander will dispatch a group of bombers with weapons having the huge destructive power to destroy all the targets in a line. Thanks to the outstanding work of our spy, the positions of all opponents' bases had been detected and marked on the map, consequently, the bombing plan will be sent to you.
Specifically, the map is expressed as a 2Dplane with some positions of enemy's bases marked on. The bombers are dispatched orderly and each of them will bomb a vertical or horizontal line on the map. Then your commanded wants you to report that how many bases will be destroyed by each bomber. Notice that a ruined base will not be taken into account when calculating the exploits of later bombers.
Input
Multiple test cases. Each test cases starts with two nonnegative integer N (N <= 100,000) and M (M <= 100,000) denoting the number of target bases and the number of scheduled bombers respectively. In the following N line, there is a pair of integers separated by single space indicating the coordinate of position of each opponent's base. The following M lines describe the bombers, each of them contains two integers c and d (0<= c <=1 , 1,000,000,000 <= d <= 1,000,000,000). c = 0 means this bomber will bomb the line x = d, c = 1 means this bomber will bomb the line y = d.
The input ends with N = M = 0.
Output
For each test case, output M lines, the ith line contains a single integer denoting the number of bases that were destroyed by the corresponding bomber in the input. Output a blank line after each test case.
Example
Input: 3 2 1 2 1 3 2 3 0 1 1 3 0 0 Output: 2 1Warning: large input/output data, be careful with certain languages
hide comments
Rahul Lingala:
20141220 08:27:30
Can anyone give some tricky test cases? Mine is giving WA. Last edit: 20141220 08:28:52 

Pratham Khandelwal:
20111011 06:56:05
NOTE:: There can be mulitple target bases on the same location. 
Added by:  Fudan University Problem Setters 
Date:  20110908 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  ACM/ICPC Regionals, Shanghai 2011 Preliminary 