インターネットと言う広大な海は少しずつ黒く塗りつぶされていった。
ボットの反乱、DDOS攻撃の嵐、ウィルスの蔓延、
何度も何度も繰り返されたクラッカーとの戦争で、人もインターネットもボロボロになった。

人の手では、インターネットはどうにもならない。
だから人は、とんでもない時間をかけて
インターネットを復旧できる「少女」を造った。

少女は、インターネットの手当をはじめた。
果てしなく広いインターネットの世界をどうにかしようと頑張った。

まだ少女ひとりでは撚り対線を織る事くらいしかできないけど、
長い長い時がすぎてインターネットが少し復旧すれば、
みんなと一緒に頑張れるだろうという期待をこめて。

問題文

少女はかつてインターネットに存在した N 個のサービスを復旧するために日々頑張っている． 現在を 0 日目とする． インターネットがどの程度復旧しているかを復旧度という指標で表し，現在の復旧度は 0 であるとする． 少女は毎日作業をし，復旧度を 1 日につき 1 ずつ上げていく． 任意のまだ復旧していないサービス i は，復旧度が w_i 以上になると自動的に復旧する． サービス i が復旧すると，みんなが手伝ってくれることにより，復旧した次の日から x_i 日間だけ作業がはかどり，復旧度の増加が加速する． サービスには 3 つの種類があり，種類によって復旧度がどの程度増加するのかが異なる． サービスの種類を 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

入出力例

入力例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

2つ目のサービスは復旧する日にちが 3,652,425 日を超えているのでMany years laterと出力している．