Alek’s Lap Overtaking

Alek starts at position $0$ on a circular track of length $m$ at time $0$ with speed $0$. There are $n$ competitors. The i^th competitor begins moving at time \(t_i\) from position \(p_i\) with constant speed \(v_i\) (all movement is counter‐clockwise along the track). Even though every competitor runs along the track indefinitely, they start from fixed positions in the circle (positions are taken in the counterclockwise direction, where the location at distance \(x\) from position \(0\) is defined as \(x\) with \(0 \le x < m\)).

Alek does not run initially. However, when a competitor coming from behind catches up with him, he immediately starts following that competitor – adopting his speed. Moreover, if later on another competitor overtakes him with a higher speed, he switches to follow the faster competitor. In other words, at any moment, Alek’s speed equals the highest speed among all competitors who have overtaken him so far.

More formally, suppose that at some time the state of Alek is \(f(t)\) (the total distance he has traveled) and his current speed is \(u\). A competitor \(i\) (with \(v_i>u\)) who starts at time \(t_i\) from position \(p_i\) will overtake Alek for the first time at the smallest time \(t\ge \max\{t_i, t_0\}\) satisfying \[ p_i + v_i\,(t-t_i) = f(t_0) + u\,(t-t_0) + m, \] where \(t_0\) is the start time of the current phase and the extra \(m\) accounts for the fact that the competitor must complete one more lap to catch up from behind. When such an event occurs, Alek’s total distance increases by \(u\,(t-t_0)+m\) and his speed instantly becomes \(v_i\). It can be shown that for any query time \(T\) the total distance traveled by Alek is an integer.

You are given \(q\) queries. In each query you are to determine the total distance traveled by Alek at time \(T_i\). Note that there may be multiple test cases.

inputFormat

The first line contains an integer \(K\), the number of test cases. For each test case, the input is structured as follows:

1. A line containing an integer \(m\) \((1 \le m \le 10^9)\), the length of the circular track.
2. A line containing two integers \(n\) and \(q\) \((1 \le n, q \le 10^5)\): the number of competitors and the number of queries.
3. Then follow \(n\) lines, each with three integers \(t_i\), \(p_i\) and \(v_i\) \((0 \le t_i \le 10^9,\ 0 \le p_i < m,\ 1 \le v_i \le 10^9)\), describing the \(i^\text{th}\) competitor.
4. Then follow \(q\) lines, each with a single integer \(T_i\) \((0 \le T_i \le 10^9)\), representing a query time.

All numbers are separated by spaces or newlines.

outputFormat

For each test case output \(q\) lines. The \(i^\text{th}\) line should contain a single integer: the total distance Alek has traveled at time \(T_i\).

sample

3
10
2 2
0 0 5
1 5 7
2
5

12
33