这是一个美好的夏日，Alice 想要进行一次一日游。她住在坦佩雷（Tampere），想要前往波尔沃（Porvoo）享受老城风光和周边自然。Alice 不仅热爱旅行，也热爱规划。

她绘制了一张前往波尔沃的最美路径地图。在旅途中，她需要依次经过 $n$ 个城市，其中坦佩雷是第一个城市，波尔沃是最后一个城市。这些城市由道路连接，每条道路连接两个相邻的城市，且每对相邻城市之间至少有一条道路。

在从一个城市开车前往下一个城市时，Alice 需要选择走哪条路。有些道路是柏油路面，有些是碎石路，还有些道路上有桥梁，无法承受过重的车辆。对于每条道路，已知其通行所需的时间以及允许安全通行的车辆最大重量。

图 E.1：第二个样例输入的示意图。对于重量为 31 的汽车，从坦佩雷到波尔沃的红色路径是最佳选择。

Alice 收集了许多不同重量的汽车，但她还不确定这次一日游要用哪一辆。由于她想在波尔沃尽可能多地享受时光，她希望你帮她找出每辆车的最小旅行时间。

输入格式

输入包含： 两个整数 $n$ 和 $m$ ($2 \le n \le 10^5, n - 1 \le m \le 10^5$)，分别表示城市数量和连接数量。城市编号从 $1$ 到 $n$，坦佩雷是城市 $1$，波尔沃是城市 $n$。 $m$ 行，每行包含三个整数 $i, d$ 和 $c$ ($1 \le i < n, 1 \le d \le 10^4, 1 \le c \le 10^6$)，描述了一条连接城市 $i$ 和城市 $i+1$ 的道路，其通行时间为 $d$ 分钟，且允许重量不超过 $c$ 公斤的车辆通行。 一个整数 $q$ ($1 \le q \le 10^5$)，表示 Alice 收集的汽车数量。 $q$ 行，其中第 $i$ 行包含一个整数 $w_i$ ($1 \le w_i \le 10^6$)，表示第 $i$ 辆车的重量（单位：公斤）。

对于每个 $i$ ($1 \le i < n$)，城市 $i$ 到城市 $i+1$ 之间至少有一条连接。

输出格式

输出 $q$ 行，其中第 $i$ 行描述 Alice 使用第 $i$ 辆车从坦佩雷到达波尔沃所需的最短时间（单位：分钟）。如果对于第 $i$ 辆车不存在可行的路径，则输出 impossible。

样例

输入 1

2 2
1 100 300
1 1 30
5
400
500
300
20
1

输出 1

impossible
impossible
100
1
1

输入 2

5 7
1 200 30
2 200 31
3 200 32
4 200 33
1 5000 33
2 5000 33
3 5000 33
3
30
31
33

输出 2

800
5600
15200

输入 3

2 3
1 3 3
1 4 2
1 2 1
3
1
3
2

输出 3

2
3
3