AT_kupc2012_6.Acceleration of Network

互联网这片广阔的海洋逐渐被黑暗所覆盖。
机器人的叛乱，DDOS攻击的风暴，病毒的蔓延，
在与黑客反复交战的过程中，人类和互联网都变得支离破碎。

人类无法拯救互联网。
因此，人类花费了很长的时间，
创造了一个可以恢复互联网的“少女”。

少女开始治疗互联网。
她努力尝试修复广阔无边的互联网世界。

虽然少女目前只能进行一些基础工作，
但随着漫长的时间流逝，一旦互联网稍微恢复，
她就有望在大家的帮助下共同努力。

问题描述

少女每天都在努力，恢复互联网上曾经存在的 $ N $ 个服务。
将当前日期设定为第 0 天。
用“恢复度”作为一个指标来表示互联网的恢复程度，当前的恢复度为 0。
少女每天工作，每天的恢复度增加 1。
任何尚未恢复的服务 $ i $ ，当恢复度达到 $ w_i $ 以上时，该服务将自动恢复。
一旦服务 $ i $ 恢复，由于大家的帮助，从恢复的第二天开始，持续 $ x_i $ 天的工作将加快恢复度的增长。
服务分为三种类型，不同类型的服务增加恢复度的速度也不同。
将服务的类型用编号 0, 1, 2 表示。
设服务 $ i $ 的类型为 $ t_i (\in {0, 1, 2}) $ ，
则服务 $ i $ 恢复后的第 $ d-1 $ 天到第 $ d $ 天（ $ 1 ≤ d ≤ x_i) $ ，
如果 $ t_i=0 $ ，则增加 1，
如果 $ t_i=1 $ ，则增加 $ d $ ，
如果 $ t_i=2 $ ，则增加 $ d^2 $ ，这些增加都是在少女的工作之外进行的。
此外，如果同时有多个服务恢复，每个服务都将独立并行地增加恢复度。

由于少女认为服务恢复需要很长时间，她决定从现在开始研究服务何时恢复。
另外，她也对某一天 $ y_j $ 的恢复度感兴趣，因此她决定研究 $ Q $ 天的情况。

输入如下格式给出。

$ N Q $

$ w_1 $ $ t_1 $ $ x_1 $

$ ... $

$ w_N $ $ t_N $ $ x_N $

$ y_1 $

$ ... $

$ y_Q $

首先输出 $ N $ 行，第 $ i $ 行输出服务 $ i $ 恢复的日期。然后输出 $ Q $ 行，第 $ j $ 行输出在第 $ y_j $ 天的恢复度。
如果服务恢复的日期超过 3,652,425 天，则输出Many years later。

约束

• $ 0 \leq N \leq 10^5 $
• $ 1 \leq Q \leq 10^5 $
• $ 0 \leq w_i \lt 2^{60} $
• $ w_i \leq w_{i+1} (1 \leq i \lt N) $
• $ t_i \in {0, 1, 2} $
• $ 1 \leq x_i \leq 10^4 $
• $ 0 \leq y_j \leq 3,652,425 $
• $ y_j \lt y_{j+1} (1 \leq j \lt Q) $
• 所有输入均为整数。

注意

• 第 0 天的恢复度为 0。
• 当 $ w_i=0 $ 时，服务 $ i $ 将在第 0 天恢复。

入出力示例

输入示例1

3 11
1 0 2
4 1 3
7 2 4
0
1
2
3
4
5
6
7
8
9
10

输出示例1

1
3
4
0
1
3
5
7
11
19
29
46
47
48

输入示例2

5 5
10000 0 20
10000 1 30
10000 0 40
10000 2 70
30000 2 10000
5000
10000
15000
20000
25000

输出示例2

10000
10000
10000
10000
10039
5000
10000
40711690801
329498273301
333383477320

输入示例3

2 2
3652425 0 1
3652426 2 10000
3652424
3652425

输出示例3

3652425
Many years later
3652424
3652425

作者：森槙悟
测试：田村和範
题目来源：AtCoder