P11290 [MX-S6-T2] "KDOI-11" Spaceship

Original link: .

Xun built a very powerful spaceship. To test her spaceship, Xun built an infinitely long ray starting from the origin as the runway. There are $n$ fuel stations on the runway. The $i$-th station is at position $p_i$ from the origin. Xun can spend $t_i$ time here to add fuel of type $x_i$. **Fuel at the same station cannot be added twice.** **It is guaranteed that $\boldsymbol{1\leq x_i\leq 4}$ and $\boldsymbol{x_i}$ is an integer.** This spaceship is powerful in two aspects: - Its fuel consumption is extremely low and can be ignored in this problem. That is, **we do not consider the case where fuel runs out.** - If fuel of type $x$ is added, **the spaceship's speed increases from $v$ to $v\times x$.** Note that **the effects of fuels can stack.** Now, Xun gives $q$ queries. For each query, Xun sets the destination at position $y_i$ on the runway from the origin. Starting from the origin, the spaceship's speed is set to $1$ unit per time. For each fuel station passed, you may freely choose whether to refuel. You need to tell Xun the minimum time needed to reach the destination (i.e., $y_i$) for each query.

The first line contains two positive integers $n, q$, representing the number of fuel stations and the number of queries. The next $n$ lines each contain three positive integers $p_i, t_i, x_i$, representing the distance of the $i$-th fuel station from the origin, the time required to refuel, and the fuel type. The fuel stations are given in strictly increasing order of $p_i$, i.e., $p_i < p_{i + 1}$. It is guaranteed that $1\leq x_i\leq 4$. The next line contains $q$ positive integers $y_1, \ldots, y_q$, representing the queries.

Output $q$ lines, each containing a non-negative real number, representing the answer. This problem uses a **custom checker** to verify your output. You only need to ensure that the relative or absolute error between your answer and the standard answer does not exceed $10^{-6}$. That is, for each query, suppose your answer is $x$ and the standard answer is $y$. If $\frac{\lvert x-y\rvert}{\max(1,\lvert y\rvert)}\leq 10^{-6}$, then your answer is considered correct.

**[Sample Explanation #1]** - For query $y_1=1$, do not refuel, and the required time is $1$. - For query $y_2=4$, do not refuel, and the required time is $4$. - For query $y_3=10$, refuel with type $2$ at fuel station $2$ located $3$ units from the origin. The speed increases to $2$, and the required time is $3+1+\frac{10-3}{2}=7.5$. **[Sample #2]** See `ship/ship2.in` and `ship/ship2.ans` in the attachment. This sample satisfies the constraints of test points $1\sim 3$. **[Sample #3]** See `ship/ship3.in` and `ship/ship3.ans` in the attachment. This sample satisfies the constraints of test points $5\sim 7$. **[Sample #4]** See `ship/ship4.in` and `ship/ship4.ans` in the attachment. This sample satisfies the constraints of test points $18\sim 20$. **[Constraints]** For all testdata, it is guaranteed that: $1\leq n\leq 10^5$, $1\leq q\leq10^5$, $1\leq p_1