Background

Original link: https://oier.team/problems/S6B.

Problem Description

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.

Input Format

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 Format

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.

4 4
1 1 1
3 1 2
8 5 2
10 100 3
1 4 10 1000

1
4
7.5
194.5

Hint

[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<p_2<\dots<p_n\leq 10^9$, $1\leq t_i\leq10^9$, $1\leq x_i\leq4$, $1\leq y_i\leq 10^9$.

Translated by ChatGPT 5