Background

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

Problem Description

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.

Input Format

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.

Output Format

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

1
3 30 8
0 2 1
6 5 2
25 4 4
1
5
9
10
11
12
13
14

0
8
16
19
23
27
31
36

Hint

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