M. The business man
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
business.in
output
standard output

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.

Input

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.

Output

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.

Example
Input
1
3 3
1 100 300
3 5 300
4 3 10
2 100
5 6
50 100
Output
1 2 1