题目背景

原题链接：https://oier.team/problems/94。

题目描述

巡造了一个很牛的飞船，巡为了测试她的飞船，造了一条无限远的从起点出发的射线作为跑道。在跑道上有 $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}$，则你的答案被认为是正确的。

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

1
4
7.5
194.5

提示

【样例解释 #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<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$。

测试点编号	$n\leq$	$q\leq$	$x_i\in$	$p_i,y_i\leq$
$1\sim 3$	$10$		$\{1,2,3,4\}$	$10^9$
$4$	$10^5$		$\{1\}$
$5\sim 7$	$100$		$\{1,2,3,4\}$	$1000$
$8\sim 9$	$10^5$	$10^5$	$\{1,2\}$	$10^9$
$10\sim 13$			$\{1,2,4\}$
$14\sim 17$		$10$	$\{1,2,3,4\}$
$18\sim 20$		$10^5$