インターネットと言う広大な海は少しずつ黒く塗りつぶされていった。
ボットの反乱、DDOS攻撃の嵐、ウィルスの蔓延、
何度も何度も繰り返されたクラッカーとの戦争で、人もインターネットもボロボロになった。
人の手では、インターネットはどうにもならない。
だから人は、とんでもない時間をかけて
インターネットを復旧できる「少女」を造った。
少女は、インターネットの手当をはじめた。
果てしなく広いインターネットの世界をどうにかしようと頑張った。
まだ少女ひとりでは撚り対線を織る事くらいしかできないけど、
長い長い時がすぎてインターネットが少し復旧すれば、
みんなと一緒に頑張れるだろうという期待をこめて。
少女はかつてインターネットに存在した N 個のサービスを復旧するために日々頑張っている. 現在を 0 日目とする. インターネットがどの程度復旧しているかを復旧度という指標で表し,現在の復旧度は 0 であるとする. 少女は毎日作業をし,復旧度を 1 日につき 1 ずつ上げていく. 任意のまだ復旧していないサービス i は,復旧度が wi 以上になると自動的に復旧する. サービス i が復旧すると,みんなが手伝ってくれることにより,復旧した次の日から xi 日間だけ作業がはかどり,復旧度の増加が加速する. サービスには 3 つの種類があり,種類によって復旧度がどの程度増加するのかが異なる. サービスの種類を 0, 1, 2 の番号で表すとする. サービス i の種類を ti (∈ {0, 1, 2}) とすると, サービス i が復旧してから d-1 日目から d 日目にかけて (1 ≤ d ≤ xi), ti=0 の場合は 1, ti=1 の場合は d, そして ti=2 の場合は d2 だけ,少女の作業とは別に復旧度が増加する. また,同時に複数のサービスが復旧している場合,それぞれのサービスは独立に並行して復旧度を増加させる.
少女はサービスが復旧するまでにとんでもない時間がかかると思ったので,現在から何日目にサービスが復旧するか調べることにした. またある日にち yj に復旧度がいくらになっているかも気になったので,それも Q 日分だけ調べることにした.
入力は以下の形式で与えられる.
N Q w1 t1 x1 ... wN tN xN y1 ... yQ
最初に N 行出力し,i 行目にはサービス i の復旧する日にちを出力せよ.次に Q 行出力し,j 行目には yj 日目に復旧度がいくらになっているかを出力せよ.
サービスが復旧する日にちが 3,652,425 を超える場合はMany years later
と出力せよ.
この問題の判定には,15 点分のテストケースのグループが設定されている.このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす.
3 11 1 0 2 4 1 3 7 2 4 0 1 2 3 4 5 6 7 8 9 10
1 3 4 0 1 3 5 7 11 19 29 46 47 48
5 5 10000 0 20 10000 1 30 10000 0 40 10000 2 70 30000 2 10000 5000 10000 15000 20000 25000
10000 10000 10000 10000 10039 5000 10000 40711690801 329498273301 333383477320
2 2 3652425 0 1 3652426 2 10000 3652424 3652425
3652425 Many years later 3652424 3652425
2つ目のサービスは復旧する日にちが 3,652,425 日を超えているのでMany years later
と出力している.