Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3299
Fall the Brick

Time Limit: 3 Seconds      Memory Limit: 32768 KB

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.


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 li, ri (0 <= li < ri <= 30000000). li and ri is the x-coordinates for the left side and the right side of the line of bricks. m lines follow, each contains three integers ai, bi, and hi (0 <= ai < bi <= 30000000; 0 < hi < 1000000000), which means that board i is at height hi and the extreme points are ai and bi. You may assume no two boards with same height will overlap with each other.


For each case, print m lines. The ith 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


Author: CHEN, Zhangyi
Source: ZOJ Monthly, February 2010
Submit    Status