Rolete

Ένα Σάββατο ο Λούκα ξύπνησε από ένα απογευματινό υπνάκο και θυμήθηκε: σήμερα είναι το COCI! Υπήρχε μόνο ένα πράγμα που έπρεπε να κάνει πριν από τον διαγωνισμό: να ανυψώσει τα στόρια του.

Ο Λούκα έχει ~n~ στόρια στο δωμάτιό του, όπου το ~i~-στό στόρι είναι χαμηλωμένο κατά ~a_i~ εκατοστά από την κορυφή του παραθύρου. Μπορεί να ανυψώσει τα στόρια με δύο τρόπους:

• Μπορεί να ξεκινήσει να ανυψώνει ένα οποιοδήποτε στόρι χειροκίνητα. Με αυτήν τη μέθοδο, του παίρνει ~t~ δευτερόλεπτα για να ανυψώσει το στόρι κατά 1 εκατοστό.
• Μπορεί να πατήσει ένα κουμπί, που ξεκινά την ανύψωση όλων των παράλληλα με την ίδια ταχύτητα. Η ταχύτητα με την οποία ανυψώνονται τα στόρια με το κουμπί καθορίζεται ως εξής: Αν όλα τα ρολά εξακολουθούν να ανυψώνονται, τότε κάθε ένα θα ανυψωθεί κατά ~1~ εκατοστό σε ~s~ δευτερόλεπτα. Αν ~r~ ρολά έχουν ήδη ανυψωθεί στην κορυφή, αυτό επιβραδύνει το σύστημα. Τότε θα χρειαστούν ~s + k \ast r~ δευτερόλεπτα για να ανυψωθούν όλα τα υπόλοιπα ρολά κατά ~1~ εκατοστό.

Ο COCI ετοιμάζεται να ξεκινήσει και ο Λούκας θέλει να ανυψώσει τα στόρια του το συντομότερο δυνατόν. Εν τω μεταξύ, ο αδερφός του Μαρίν μπήκε στο δωμάτιό του και του έθεσε ~q~ ερωτήσεις: Ποιος είναι ο ελάχιστος χρόνος που χρειάζεσαι για να ανυψώσεις τα στόρια έτσι ώστε να είναι όλα χαμηλωμένα τουλάχιστον κατά ~h~ εκατοστά; Ο Μαρίν ενδιαφέρεται για την απάντηση σε κάθε ερώτηση, λαμβάνοντας υπόψη την αρχική κατάσταση που βρίσκονται τα στόρια.

Συνειδητοποίησαν ότι δεν υπάρχει αρκετός χρόνος για να το σκεφτούν πριν τον COCI. Ευτυχώς, το πρόβλημα τους εμφανίστηκε επίσης εδώ! Βοηθήστε τους να το λύσουν!

Σημείωση: Ο Λούκα θα ανυψώσει πάντα το στόρι κατά μια ακέραια τιμή εκατοστών.

Είσοδος

Η πρώτη γραμμή θα περιέχει τους ακέραιους αριθμούς ~n~, ~t~, ~s~ και ~k\;(1 \le n, t, s \le 10^5,\; 0 \le k \le 10^5)~, τον αριθμό από στόρια, τον χρόνο που απαιτείται για να ανυψωθεί ένα στόρι με το χέρι, τον χρόνο που απαιτείται για να ανυψωθεί ένα στόρι με ένα κουμπί και τον παράγοντα επιβράδυνσης της παράλληλης ανύψωσης.

Η δεύτερη γραμμή θα περιέχει ~n~ ακεραίους ~a_i\;(0 \le a_i \le 10^5)~, την αρχική κατάσταση από τα στόρια.

Η τρίτη γραμμή θα περιέχει τον ακέραιο αριθμό ~q\;(1 \le q \le 10^5)~, τον αριθμό των ερωτήσεων.

Η τέταρτη γραμμή θα περιέχει ~q~ ακεραίους ~h_i\;(0 \le h_i \le 10^5), το μέγιστο απαιτούμενο ύψος του στοριού.

Έξοδος

Στην πρώτη και μοναδική γραμμή εκτυπώστε ~q~ αριθμούς, όπου ο ~i~-οστός από αυτούς θα είναι ο ελάχιστος χρόνος που χρειάζεται για να ανυψωθούν τα στόρια έτσι ώστε να χαμηλώσουν τουλάχιστον κατά ~h_i~ εκατοστά.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	16	~n,\;,q,\;a_i,\;h_i \le 100~
2	26	~K = 0~
3	32	~q = 1~
4	36	Κανένας επιπλέον περιορισμός.

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

input

3 2 5 1
2 2 4
3
2 0 1

output

4 14 9

Επεξήγηση του πρώτου παραδείγματος: Για να έχει όλα τα στόρια χαμηλωμένα κατά το πολύ ~2~ εκατοστά, ο Λούκα χρειάζεται να ανυψώσει χειροκίνητα το τρίτο στόρι κατά ~2~ εκατοστά. Ο γρηγορότερος τρόπος για να το κάνει αυτό είναι να το ανυψώσει χειροκίνητα. Αυτό θα του πάρει ~4~ δευτερόλεπτα.

Αν όλα τα στόρια χρειάζεται είναι πλήρως ανυψωμένα, ο Λούκα μπορεί πρώτα να ανυψώσει χειροκίνητα το τρίτο στόρι κατά ~2~ εκατοστά. Τώρα μπορεί να πατήσει το κουμπί και να αφήσει τα στόρια να ανυψωθούν παράλληλα κατά ~2~ εκατοστά. Συνολικά, αυτό θα πάρει ~4 + 10 = 14~ δευτερόλεπτα.

Ομοίως, αν τα στόρια χρειάζεται να είναι χαμηλωμένα κατά το πολύ ~1~ εκατοστό, ο Λούκα θα ανυψώσει πρώτα το τρίτο στόρι κατά ~2~ εκατοστά και στη συνέχεια θα ανυψώσει όλα τα στόρια μαζί κατά ~1~ εκατοστό. Ο συνολικός χρόνος ανύψωσης θα είναι ~9~ δευτερόλεπτα.

input

2 3 4 0
3 1
3
3 2 0

output

0 3 10

input

4 3 10 3
2 4 5 6
3
4 3 0

output

9 18 47