P9933 [NFLSPC #6] 9.pop_book();

*Alek Sui* is running laps on the playground. He feels upset when he sees someone overtake him, so he uses the following strategy.

On a circular playground of length $m$, there are $n$ people. Person $i$ starts from position $p_i$ at time $t_i$ and moves at speed $v_i$ units per second. Now at time $0$, *Alek Sui* is at position $0$ with speed $0$, and he will follow the fastest person who passes by him. There are $q$ queries asking for the distance *Alek Sui* has moved at time $T_i$. It can be proven that this is an integer. Note: The position that is $x$ ($0\leq x < m$) units counterclockwise from position $0$ is called position $x$. Everyone moves counterclockwise. Multiple test cases.

The first line contains an integer $T$ indicating the number of test cases. For each test case: - The first line contains three integers $n, m, q$, representing the number of people, the playground length, and the number of queries. - The next $n$ lines each contain three integers $p_i, v_i, t_i$, representing the starting position of person $i$, the moving speed (units per second), and the starting time. - The next $q$ lines each contain one integer $T_i$, representing a query.

For each query, output one line with an integer representing the answer.

For all testdata, $1\leq T\leq 10 ^ 3$, $1\leq n, \sum n\leq 5\times 10 ^ 5$, $1\leq m, q, \sum q \leq 10 ^ 6$, $1\leq v_i, t_i, T_i\leq 10 ^ 9$, $0\leq p_i < m$. It is guaranteed that $t_i$ is non-decreasing and $T_i$ is strictly increasing. - Subtask 1 ($10$ points): $n\leq 5$. - Subtask 2 ($10$ points): $n\leq 50$. - Subtask 3 ($20$ points): $n\leq 500$. - Subtask 4 ($20$ points): $n\leq 5\times 10 ^ 3$. - Subtask 5 ($20$ points): $n\leq 5\times 10 ^ 4$. - Subtask 6 ($20$ points): no special constraints. **Please note that the subtasks do not guarantee the order of magnitude of $\sum q$.** The I/O size of this problem is large. It is recommended to use `scanf/printf`, or disable synchronization for `cin/cout`, or use fast input and fast output. Source: NFLSPC #6 I by Alex_Wei Translated by ChatGPT 5