International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2018) |
---|
Finished |
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:
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
Name |
---|