405565: GYM101992 M The business man

Badry is tired of programming, that is why he wanted to try his chances in business world. Badry opened a company that trades in antiques. The company owns $$$N$$$ different shops where the $$$i_{th}$$$ shop has its location $$$X_i$$$ on the $$$OX$$$ axis and its product has initial quality $$$Q_i$$$. Moreover, there are two more strange facts about these shops:

• The first one is that the delivery cars of the $$$i_{th}$$$ shop can only deliver products to customers with locations in the range $$$[X_i, X_i + R_i]$$$.
• The second fact is that the quality of a product increases by one for each unit distance, which means that if some shop with location $$$X$$$ and initial quality $$$Q$$$ delivered its product to a customer at location $$$Y$$$ the quality of the product will be considered as ($$$Q+Y-X$$$).

Currently, Badry has $$$M$$$ orders from $$$M$$$ different customers where the $$$i_{th}$$$ customer is located at position $$$Y_i$$$ and requesting his product to be with quality at least $$$D_i$$$.

Can you help Badry by determining the number of shops that can serve each customer ? You can assume that each shop has infinite number of products.

The first line of input contains the number of test cases $$$T$$$. Each test case starts with a line containing two integers $$$N$$$ and $$$M$$$ the number of shops and the number of customers respectively, where $$$1\leq N, M \leq 10^5$$$.

Each of the next $$$N$$$ lines contains three integers $$$X_i$$$, $$$Q_i$$$ and $$$R_i$$$ representing the $$$i_{th}$$$ shop, where $$$1 \leq X_i, Q_i, R_i \leq 10^9$$$.

Each of the following $$$M$$$ lines contains two integers $$$Y_i$$$ and $$$D_i$$$ representing the $$$i_{th}$$$ customer, where $$$1 \leq Y_i, D_i \leq 10^9$$$. All the positions of the shops are given in a non-decreasing order. Also all positions of the customers are given in a non-decreasing order.

For each test case output a single line containing $$$M$$$ space-separated integers, the number of possible serving shops for each customer.

Please output the answer for customers in the same order they appeared in input.

1
3 3
1 100 300
3 5 300
4 3 10
2 100
5 6
50 100

1 2 1