Spacecraft Refueling Optimization

You have built an extraordinary spaceship and want to test it. To do so, an infinite ray starting at the origin is used as a runway. Along the runway there are n fueling stations. The i-th station is located at distance p_i from the origin. At this station, you may spend t_i units of time to obtain fuel of type x_i (with x_i an integer satisfying \(1\le x_i\le 4\)). Note: The fuel provided at each station can only be taken once.

The spaceship has two distinguishing features:

1. Its fuel consumption is so low that it can be ignored (i.e. the spaceship never runs out of fuel).
2. If you add fuel of type \(x\), the spaceship's speed immediately increases from \(v\) to \(v \times x\). Furthermore, the effects of fuels accumulate multiplicatively.

You are given \(q\) queries. In each query, the destination is set at a distance \(y_i\) along the runway. Initially, the spaceship is at the origin with a speed of \(1\). As the spaceship travels toward \(y_i\), you may choose at any encountered fueling station whether to refuel (thus earning a speed boost) or skip it.

The travel time is computed as follows: if you are at position \(a\) with speed \(v\) and travel to position \(b\) (\(b > a\)), the travel time is \((b-a)/v\). If you decide to refuel at a station, add the station's refueling time t_i, and note that the spaceship’s speed is then updated to \(v\times x_i\). The objective is to minimize the total time (travel time plus refueling time) needed to exactly reach the destination \(y_i\).

Input constraints:

• \(1 \le n, q \)
• \(p_i, t_i\) are positive numbers; \(x_i\) is an integer with \(1\le x_i\le 4\).

Input Format:

n q
p1 t1 x1
p2 t2 x2
... (n lines total)
y1
y2
... (q lines total)

Output Format:

For each query, output the minimum time required to reach \(y_i\).

Note: You may assume that the spaceship always moves forward along the runway and that refueling decisions are made only at stations with\( p_i\le y_i\).

inputFormat

The first line contains two integers \(n\) and \(q\) representing the number of fueling stations and the number of queries, respectively. The following \(n\) lines each contain three numbers \(p_i\), \(t_i\), and \(x_i\) which represent the position, refueling time, and fuel type of the \(i\)-th station. It is guaranteed that \(1\le x_i\le 4\) and \(x_i\) is an integer. The next \(q\) lines each contain a single number \(y_i\) indicating the destination's position on the runway.

outputFormat

For each query, print one line containing the minimum time required to reach the destination \(y_i\). The answer will be considered correct if its absolute or relative error does not exceed \(10^{-6}\).

sample

3 3
2 1 2
4 2 3
6 1 4
3
6
10

3.000000
5.000000
6.500000

</p>