На благо накосена површина истовремено од врвот се пуштаат N кликери (мали метални топчиња) и тие се тркалаат надолу по површината (еден покрај друг на засебни паралелни патеки). Површината се состои од 3 последователни дела, секој со должина од 100 метри. Таа е многу благо накосена па кликерите се бавни и за да поминат еден метар им треба меѓу една и педесет секунди. За секој кликер се знае колку секунди му треба да помине еден метар, и тоа може да е различно за секој од трите дела (една „брзина“ за првите 100 метри, друга за вторите и трета за третите).

Но, постои и можност за брзо движење. На површината, на неколку места се поставени акцелератори кои можат да ги забрзаат кликерите. Акцелераторот е поставен на одредено растојание од почетокот, преку целата површина и сите кликери проаѓаат преку него кога се на тоа растојание од почетокот. Кога кликер А ќе дојде до акцелератор, ако до тој момент преку акцелераторот поминале X кликера (без оние кои во исти момент поминуваат со кликерот А), тогаш тој кликер следните X mod 20 метри ќе ги поминува со максималната „брзина“ од 1 секунда по метар. Ако за време на брзо движење кликерот наиде на нов акцелератор, не може да го искористи, но акцелератор кој доаѓа по завршување на брзото движење (вклучувајќи го и моментот кога брзото движење престанува) може да се искористи.

Секој акцелератор се користи од сите кликери дури и во ист момент. По завршување на брзото движење, додека нема нови акцелератори, кликерот продолжува да се движи со својата зададена брзина за соодветниот дел од површината.

Напишете програма која ќе го симулира ова тркалање. Под претпоставка дека сите кликери стартуваат во ист момент (време 0), и не си пречат меѓусебно (се тркалаат по паралелни патеки) пресметајте го за секој кликер времето (во секунди) кога стигнува на крај на површината.

Влез

Во првиот ред се наоѓа природен број N (2 ≤ N ≤ 20 000), бројот на кликери.

Во секој од следните N реда има по три природни броеви меѓу 1 и 50: зададените „брзини“ на кликерот во секунди по метар за првите, вторите и третите 100 метри.

Потоа следи природен број M (0 ≤ M < 300), бројот на акцелератори.

Ако M > 0, следи еден ред со M строго растечки природни броеви меѓу 1 и 299 – растојанија на акцелераторите од почетокот на патеката (во метри).

Подзадача 1: (15 поени) M = 1
Подзадача 2: (40 поени) N ≤ 300
Подзадача 3: (45 поени) без дополнителни ограничувања

Излез

Во N редови на излез треба да стои баранoто време (во секунди) за секој кликер посебно.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
2
1 2 3
4 5 6
0

излез
600
1500

влез
3
5 5 5
6 2 10
10 9 2
2
100 199

излез
1496
1799
2075

влез
5
2 2 2
6 6 6
8 8 8
9 9 9
10 10 10
2
297 298

излез
600
1790
2386
2676
2973

Објаснување на првиот пример: Нема акцелератори и сите кликери се тркалаат само со зададените брзини.

Објаснување на вториот пример: За кликер #1 првиот акцелератор не прави ништо бидејќи за него Х=0 (пред него тогаш нема ниеден кликер поминато преку акцелераторот), но го користи вториот бидејќи во меѓувреме го претекнал кликер #2. Кликер #1 вкупно тркала 299 метри по 5 секунди од метар и 1 метар по 1 секунда од метар.
Кликер #2 го користи првиот акцелератор (пред него тогаш има поминато еден кликер), а не го користи вториот. Тој тркала 100 метри по 6 секунди, 1 метар по 1 секунда, 99 метри по 2 секунди и 100 метри по 10 секунди.
Кликер #3 во моментите кога користи акцелератор има пред себе двајца кликери и затоа по секој акцелератор тркала 2 метри со максимална брзина. Тој тркала 100 метри по 10 секунди, 2 метри по 1 секунда, 97 метри по 9 секунди, 2 метри по 1 секунда и 99 метри по 2 секунди.

Објаснување на третиот пример: Од двата акцелератори при крајот на патеката, кликер #1 не користи ниту еден. Кликер #2 ги користи двата (по 1 метар) и потоа уште 1 метар тркала со својата зададена брзина. Кликер #3 го користи првиот акцелератор (за 2 метри) и потоа уште 1 метар тркала со својата зададена брзина. Кликери #4 и #5 го користат забрзувањето од првиот акцелератор сè до крајот на патеката.