{"raw_statement":[{"iden":"statement","content":"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_{t h}$ shop has its location $X_i$ on the $O X$ axis and its product has initial quality $Q_i$. Moreover, there are two more strange facts about these shops: \n\nCurrently, Badry has $M$ orders from $M$ different customers where the $i_{t h}$ customer is located at position $Y_i$ and requesting his product to be with quality at least $D_i$. \n\nCan 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. \n\nThe 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 <= N, M <= 10^5$. \n\nEach of the next $N$ lines contains three integers $X_i$, $Q_i$ and $R_i$ representing the $i_{t h}$ shop, where $1 <= X_i, Q_i, R_i <= 10^9$.\n\nEach of the following $M$ lines contains two integers $Y_i$ and $D_i$ representing the $i_{t h}$ customer, where $1 <= Y_i, D_i <= 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. \n\nFor each test case output a single line containing $M$ space-separated integers, the number of possible serving shops for each customer. \n\nPlease output the answer for customers in the same order they appeared in input. \n\n"},{"iden":"input","content":"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 <= N, M <= 10^5$. Each of the next $N$ lines contains three integers $X_i$, $Q_i$ and $R_i$ representing the $i_{t h}$ shop, where $1 <= X_i, Q_i, R_i <= 10^9$.Each of the following $M$ lines contains two integers $Y_i$ and $D_i$ representing the $i_{t h}$ customer, where $1 <= Y_i, D_i <= 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. "},{"iden":"output","content":"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. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N, M \\in \\mathbb{Z} $ denote the number of shops and customers, respectively.  \n- Let $ S = \\{(x_i, q_i, r_i) \\mid i \\in \\{1, \\dots, N\\}\\} $ be the set of shops, where:  \n  - $ x_i \\in \\mathbb{R} $ is the position on the $OX$ axis,  \n  - $ q_i \\in \\mathbb{Z}^+ $ is the initial quality,  \n  - $ r_i \\in \\mathbb{Z}^+ $ is the range (radius) of the shop.  \n- Let $ C = \\{(y_j, d_j) \\mid j \\in \\{1, \\dots, M\\}\\} $ be the set of customers, where:  \n  - $ y_j \\in \\mathbb{R} $ is the customer’s position,  \n  - $ d_j \\in \\mathbb{Z}^+ $ is the minimum required quality.  \n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{unknown} $ (implied by input format)  \n2. $ 1 \\le N, M \\le 10^5 $  \n3. $ 1 \\le x_i, q_i, r_i, y_j, d_j \\le 10^9 $  \n4. The sequence $ (x_1, x_2, \\dots, x_N) $ is non-decreasing.  \n5. The sequence $ (y_1, y_2, \\dots, y_M) $ is non-decreasing.  \n\n**Objective**  \nFor each customer $ j \\in \\{1, \\dots, M\\} $, compute:  \n$$  \nc_j = \\left| \\left\\{ i \\in \\{1, \\dots, N\\} \\ \\middle| \\ |x_i - y_j| \\le r_i \\ \\land \\ q_i \\ge d_j \\right\\} \\right|  \n$$  \nOutput $ c_1, c_2, \\dots, c_M $ for each test case.","simple_statement":"For each customer at position Y_i needing quality D_i, count how many shops (at position X_i with quality Q_i) satisfy: |X_i - Y_i| ≤ R_i and Q_i ≥ D_i.","has_page_source":false}