Segway

Υπάρχει ένας αγώνας Segway στην πόλη του Dubrovnik. Η πίστα αποτελείται από τρία τμήματα, το καθένα από τα οποία έχει μήκος ~100~ μέτρα – επομένως, το συνολικό μήκος της πίστας είναι ~300~ μέτρα. Βασισμένος στους περιορισμούς της μπαταρίας του Segway του/της, κάθε αναβάτης έχει μια στρατηγική: την ταχύτητα με την οποία οδηγεί στα πρώτα ~100~ μέτρα, την ταχύτητα στα επόμενα ~100~ μέτρα και την ταχύτητα στα τελευταία ~100~ μέτρα, εκτός εάν επιτρέπεται να επιταχύνει το Segway στη μέγιστη ταχύτητα (εξηγείται στην επόμενη παράγραφο). Δυστυχώς, τα Segway είναι πολύ αργά, χρειάζονται από ~1~ έως ~50~ δευτερόλεπτα για κάθε μέτρο. Επομένως, οι ταχύτητες σε αυτή την εργασία δίνονται σε δευτερόλεπτα ανά μέτρο (αντί για μέτρα ανά δευτερόλεπτο).
Κατά μήκος της πίστας υπάρχουν αρκετά σημεία επιτάχυνσης (επιταχυντές). Όταν ένας αναβάτης φτάσει έναν επιταχυντή, το Segway του έχει επιπλέον ισχύ για να οδηγεί με μέγιστη ταχύτητα 1 δευτερόλεπτο ανά μέτρο για τα επόμενα ~X~ mod ~20~ μέτρα, όπου ~X~ είναι ο αριθμός των αναβατών που ήταν αυστηρά μπροστά του τη στιγμή που έφτασε στον επιταχυντή (συμπεριλαμβανομένων όσων έχουν ήδη ολοκληρώσει τον αγώνα). Ο αναβάτης δεν μπορεί να χρησιμοποιήσει άλλον επιταχυντή πριν ξοδέψει όλη την επιπλέον ισχύ από τον προηγούμενο επιταχυντή. Εκείνη τη στιγμή, αν δεν υπάρχουν νέοι επιταχυντές, ο αναβάτης συνεχίζει να κινείται με την προεπιλεγμένη του ταχύτητα για το αντίστοιχο κομμάτι της πίστας.
Ας υποθέσουμε ότι ένας αναβάτης θα χρησιμοποιεί πάντα έναν διαθέσιμο επιταχυντή, ακόμα κι αν μπορεί να μην είναι η βέλτιστη στρατηγική. Ένας επιταχυντής μπορεί να χρησιμοποιηθεί από πολλούς αναβάτες, ακόμη και ταυτόχρονα. Το καθήκον σας είναι να γράψετε ένα πρόγραμμα που προσομοιώνει αυτόν τον αγώνα. Υποθέτοντας ότι όλοι οι αναβάτες της Segway ξεκινούν την ίδια στιγμή, εκτυπώστε την ώρα τερματισμού για τον καθένα αναβάτη σε δευτερόλεπτα.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό ~N (2 \le N \le 20\,000)~, τον αριθμό των αναβατών.
H ~K~-οστή των ακόλουθων ~N~ γραμμών περιέχει τρεις ακέραιους αριθμούς μεταξύ ~1~ και ~50~: η προεπιλεγμένη ταχύτητα του ~K~-οστου αναβάτηη στα πρώτα ~100~ μέτρα, στα επόμενα ~100~ μέτρα και στα τελευταία ~100~ μέτρα της πίστας.
Η επόμενη γραμμή περιέχει έναν ακέραιο αριθμό ~M (0 \le M \le 299)~, τον αριθμό των σημείων επιτάχυνσης.
Εάν ~M > 0~, η ακόλουθη γραμμή περιέχει μια αυστηρά αυξανόμενη ακολουθία ~M~ ακεραίων μεταξύ ~1~ και ~299~:αποστάσεις των επιταχυντών από την αρχή της πίστας σε μέτρα.

Έξοδος

Θα πρέπει να εκτυπώσετε ~N~ γραμμές, όπου η γραμμή ~K~ περιέχει τον απαιτούμενο χρόνο για τον ~K~-οστό αναβάτη.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	15	~M = 1~
2	40	~N \le 300 ~
3	45	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

2
1 2 3
4 5 6
0

output

600
1500

Επεξήγηση του 1ου παραδείγματος

Δεν υπάρχουν επιταχυντές και οι δύο αναβάτες χρησιμοποιούν τις προεπιλεγμένες ταχύτητες.

input

3
5 5 5
6 2 10
10 9 2
2
100 199

output

1496
1799
2075

Επεξήγηση του 2ου παραδείγματος

Ο αναβάτης #~1~ δεν χρησιμοποιεί τον πρώτο επιταχυντή (δεν υπάρχει κανείς μπροστά από αυτόν), αλλά χρησιμοποιεί τον δεύτερο επιταχυντή επειδή ο αναβάτης #~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~ δευτερόλεπτα το καθένα.

input

5
2 2 2
6 6 6
8 8 8
9 9 9
10 10 10
2
297 298

output

600
1790
2386
2676
2973

Επεξήγηση του 3ου παραδείγματος

Από τους δύο επιταχυντές κοντά στο τέλος της πίστας, ο αναβάτης #~1~ δεν χρησιμοποιεί κανένα. Ο αναβάτης #~2~ χρησιμοποιεί και τους δύο (για ~1~ μέτρο) και μετά οδηγεί για άλλο ~1~ μέτρο με την προεπιλεγμένη του ταχύτητα. Αναβάτης #~3~ χρησιμοποιεί το πρώτο γκάζι (για ~2~ μέτρα) και μετά οδηγεί για άλλο ~1~ μέτρο με την προεπιλεγμένη ταχύτητα. Οι αναβάτες #~4~ και #~5~ χρησιμοποιούν την επιπλέον ισχύ από το πρώτο γκάζι μέχρι το τέλος της πίστας.