
ZOJ Problem Set  3299
Now the God is very angry, so he wants to punish the lazy, greedy humans. He chooses to throw some lines of bricks (just down from the very high Heaven). These days the God lives in a 2D world, so he just throw the bricks in a vertical plane. Each time, the God throws a line of bricks. The width of each brick is 1, and the length will be given. t__nt is a hero in the world and he is trying his best to save the world. Now he has made m horizontal boards in the air with his magic power to stop the bricks. If one brick falls onto a board, it can not fall down any more. Notice that, for a line of bricks, consecutive bricks are not connected. So when some bricks touch a board, the others will continues to fall down. Now, t__nt wants to know how many bricks each board holds after the God's crazy action. He asks you, an ACMer, to help him. Input There are no more then 10 cases. There is a blank line between consecutive cases. The first line of each case contains two integers n, m (0 < n, m <= 100000), indicating the number of lines of bricks and number of horizontal boards made by t__nt. n lines follow, each contains two integers l_{i}, r_{i} (0 <= l_{i} < r_{i} <= 30000000). l_{i} and r_{i} is the xcoordinates for the left side and the right side of the line of bricks. m lines follow, each contains three integers a_{i}, b_{i}, and h_{i} (0 <= a_{i} < b_{i} <= 30000000; 0 < h_{i} < 1000000000), which means that board i is at height h_{i} and the extreme points are a_{i} and b_{i}. You may assume no two boards with same height will overlap with each other. Output For each case, print m lines. The i_{th} line means the number of bricks on board i at last. Print a blank line after each case. Sample Input 1 2 1 8 1 5 8 3 7 6 Sample Output 4 2 Author: CHEN, Zhangyi Source: ZOJ Monthly, February 2010 