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](https://atcoder.jp/contests/kupc2012/tasks/kupc2012_6)