P11290 【MX-S6-T2】「KDOI-11」飞船

原题链接：。

巡造了一个很牛的飞船，巡为了测试她的飞船，造了一条无限远的从起点出发的射线作为跑道。在跑道上有 $n$ 个加油站，第 $i$ 个在距离起点 $p_i$ 的位置，巡可以在这里花费 $t_i$ 的时间加编号为 $x_i$ 的燃油，**同一个加油站的油不能加两次**，**保证 $\boldsymbol{1\leq x_i\leq 4}$ 且 $\boldsymbol{x_i}$ 为整数**。 巡的飞船牛在两个点： - 这个飞船油量消耗极低，在本题中可以忽略不计。也就是，**我们不考虑油消耗殆尽的情况。** - 如果给飞船加编号为 $x$ 的燃油，**飞船的速度会从 $v$ 提升为 $v\times x$**。需要注意的是，**燃油的效果能叠加**。 现在，巡给出了 $q$ 次询问。每次巡会将终点设在跑道上距离起点 $y_i$ 的位置，从起点出发，将飞船速度设定为 $1$ 单位每时间，途径的每个加油站可以自由选择是否加油。你需要告诉巡每次至少需要多少时间才能到达终点（即 $y_i$）。

第一行，两个正整数 $n,q$，表示加油站个数和询问个数。 接下来 $n$ 行，每行三个正整数 $p_i,t_i,x_i$，分别表示第 $i$ 个加油站距离起点的距离、加油需要的时间和燃油的编号。加油站按 $p_i$ 严格升序给出，即 $p_i < p_{i + 1}$。保证 $1\leq x_i\leq 4$。 接下来一行，$q$ 个正整数 $y_1, \ldots, y_q$，表示询问。

$q$ 行，每行一个非负实数，表示答案。 本题使用**自定义校验器**检验你的答案是否正确，你只需要保证你的答案与标准答案相对或绝对误差不超过 $10^{-6}$ 即可。即如果对每个询问，假设你的答案为 $x$，而标准答案为 $y$，都有 $\frac{\lvert x-y\rvert}{\max(1,\lvert y\rvert)}\leq 10^{-6}$，则你的答案被认为是正确的。

**【样例解释 #1】** - 对询问 $y_1=1$，不加油，需要时间为 $1$。 - 对询问 $y_2=4$，不加油，需要时间为 $4$。 - 对询问 $y_3=10$，在位于起点 $3$ 单位距离的加油站 $2$ 加 $2$ 号燃油，速度提升为 $2$，需要时间为 $3+1+\frac{10-3}{2}=7.5$。 **【样例 #2】** 见附件中的 `ship/ship2.in` 与 `ship/ship2.ans`。 该组样例满足测试点 $1\sim 3$ 的约束条件。 **【样例 #3】** 见附件中的 `ship/ship3.in` 与 `ship/ship3.ans`。 该组样例满足测试点 $5\sim 7$ 的约束条件。 **【样例 #4】** 见附件中的 `ship/ship4.in` 与 `ship/ship4.ans`。 该组样例满足测试点 $18\sim 20$ 的约束条件。 **【数据范围】** 对于所有测试数据，保证：$1\leq n\leq 10^5$，$1\leq q\leq10^5$，$1\leq p_1