{"problem":{"name":"M. The business man","description":{"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10199M"},"statements":[{"statement_type":"Markdown","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## Input\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$. 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. \n\n## Output\n\nFor 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. \n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10199M","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}