King Gruff

Ο Βασιλιάς Gruff ο Λύκος κυβερνά μια ευτυχισμένη, ευημερούσα γη που κατοικείται από αξιολάτρευτες Αλεπούδες. Δυστυχώ για αυτές, δεν είναι καθόλου καλός βασιλιάς, και θέλει να κάνει τη ζωή τους άθλια!

Η χώρα του έχει ~N~ (~1 \le N \le 10^5~) πόλεις, με ~M~ (~0 \le M \le 10^5~) δρόμους να περνούν ανάμεσά τους. Ο ~i~-οστος δρόμος επιτρέπει σε κάποιον να ταξιδέψει από την πόλη ~X_i~ σε μια διαφορετική πόλη ~Y_i~ (~1 \le X_i, Y_i \le N~ ), σε αυτή μόνο την κατεύθυνση και έχει μήκος ~L_i~ (~1 \le L_i \le 10^4~) και κόστος τερματισμού ~C_i~ (~1 \le C_i \le 10^4~). Μπορεί να υπάρχουν πολλοί δρόμοι που περνούν μεταξύ ενός ζεύγους πόλεων, ακόμη και προς την ίδια κατεύθυνση.

Ο Βασιλιάς Gruff αντιπαθεί ιδιαίτερα τις Αλεπούδες που ζουν σε δύο διαφορετικές πόλεις ~A~ και ~B~ (~1 \le A, B \le N~), και θα ήθελε να καταστήσει πιο άβολο (ή ακόμα και αδύνατο) να ταξιδεύουν από την πόλη ~A~ στην πόλη ~B~. Συγκεκριμένα, θα επιλέξει μια τιμή απόστασης ~D~ (~1 \le D \le 10^9~) και στη συνέχεια θα κλείσει ταυτόχρονα κάθε δρόμο στο βασίλειό του που αποτελεί μέρος τουλάχιστον ενός μονοπατιού από την πόλη ~A~ στην πόλη ~B~ με σύνολικό μήκος όχι περισσότερο από ~D~. Για κάθε τέτοιο δρόμο, ωστόσο, θα πρέπει να βάλει χέρι στο βασιλικό θησαυροφυλάκιό του και να πληρώσει το κόστος διακοπής λειτουργίας του. Ένα μονοπάτι αποτελείται από μια ακολουθία δρόμων έτσι ώστε κάθε δρόμος (εκτός από τον πρώτο) να ξεκινά από την πόλη στην οποία τελείωσε ο προηγούμενος δρόμος και μπορεί να επισκέπτεται μια πόλη ή δρόμο πολλές φορές.

Ο Gruff δυσκολεύεται να αποφασίσει ποια τιμή του ~D~ θα επιλέξει, ωστόσο - μία μεγαλύτερη τιμή θα έκανε τα πράγματα πιο άβολα για τις Αλεπούδες-υπηκόους του, αλλά μπορεί να του κοστίσει περισσότερα χρήματα επισης! Ως εκ τούτου, θα εξετάσει ~Q~ (~1 \le Q \le 10^5~) διαφορετικές τιμές, ~D_1, D_2, ..., D_Q~. Για την κάθε τιμή, θα ήθελε να μάθει πόσα χρήματα των φορολογουμένων θα πρέπει να δαπανηθούν για να κλείσουν όλοι οι δρόμοι που βρίσκονται σε τουλάχιστον ένα αρκετά σύντομο μονοπάτι από την πόλη ~A~ στην πόλη ~B~. Εφόσον δεν σας αρέσουν ούτε σε εσάς οι Αλεπούδες, έχετε συμφωνήσει να βοηθήσετε τον Λύκο να γράψει ένα πρόγραμμα για να το υπολογίσει αυτό!

Είσοδος

Η πρώτη γραμμή περιέχει ~4~ ακέραιους, καθέναν χωρισμένο με ένα κενό:

• ~N~ (~1 \le N \le 10^5~), τον αριθμό των πόλεων, ακολουθούμενο από

• ~M~ (~0 \le M \le 10^5~), τον αριθμό των δρόμων, ακολουθούμενο από

• ~A~ (~1 \le A \le N~), την αρχική πόλη, ακολουθούμενο από

• ~B~ (~1 \le B \le N~), την τελική πόλη.

Καθεμία από τις επόμενες ~M~ γραμμές περιέχει τέσσερις, χωρισμένους με κενό, ακέραιους ~X_i, Y_i, L_i~ και ~C_i~, που περιγράφουν τον δρόμο από το ~X_i~ στο ~Y_i~ με μήκος ~L_i~ και κόστος διακοπής ~C_i~ (όπου ~1 \le X_i, Y_i \le N~, ~1 \le L_i, C_i \le 10^4~).

Η επόμενη γραμμή περιέχει το ~Q~ (~1 \le Q \le 10^5~), τον αριθμό από τις διαφορετικές τιμές απόστασης που πρέπει να εξετάσετε.

Οι επόμενες ~Q~ γραμμές καθεμία περιέχουν έναν ακέραιο ~D_i~ (~1 \le D_i \le 10^9~), ο οποίος είναι η τιμή της απόστασης για να εξετάσετε όταν κλείνετε τους δρόμους.

Βαθμολογία

Ισχύουν οι ακόλουθες συνθήκες για τα δεδομένα εισόδου:

• Για τις περιπτώσεις δοκιμής αξίας έως 20% των βαθμών, ~N \le 500~
• Για τις περιπτώσεις δοκιμής αξίας έως 20% των βαθμών, ~Q = 1~
• Για τις περιπτώσεις δοκιμής αξίας έως 80% των βαθμών, ~Q \le 20~

Έξοδος

Η έξοδος αποτελείται από ~Q~ γραμμές, καθεμία με έναν ακέραιο, που αντιπροσωπεύει το συνολικό κόστος που απαιτείται για να κλείσουν όλοι οι απαραίτητοι δρόμοι δεδομένης μίας τιμής απόστασης ~D_i~, για ~i = 1 ... Q~.

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

input

4 5 1 3
1 2 5 1
1 2 8 50
2 3 2 15
3 1 80 1000
3 4 1 1
4
8
6
90
94

output

16
0
66
1066

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

Ένας χάρτης της χώρας φαίνεται παρακάτω, με κάθε δρόμο να επισημαίνεται μόνο με το μήκος του:

Αν ~D = 8~, ο πρώτος και ο τρίτος δρόμος πρέπει να κλείσουν, καθώς είναι και οι δύο μέρος ενός μονοπατιού από την πόλη ~1~ στην πόλη ~3~ μήκους ~7~. Αυτό συνεπάγεται ένα συνολικό κόστος ~1 + 15 = 16~.

Αν ~D = 6~, κανένας δρόμος δεν χρειάζεται να κλείσει, καθώς δεν υπάρχει κανένα μονοπάτι από την πόλη ~1~ στην πόλη ~3~ με συνολικό μήκος ~6~ ή λιγότερο.

Αν ~D = 90~, οι πρώτοι τρεις δρόμοι πρέπει να κλείσουν.

Αν ~D = 94~, θα πρέπει να κλείσει επιπλέον και ο τέταρτος δρόμος, καθώς βρίσκεται σε ένα μονοπάτι από την πόλη ~1~ στην πόλη ~3~ μήκους ακριβώς ~94~, αποτελούμενο από τον πρώτο, τρίτο, τέταρτο, πρώτο και μετά τρίτο δρόμο.

input

4 3 1 2
2 1 1 1
3 4 10000 10000
4 3 10000 10000
1
1000000000

output

0

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

Ο χάρτης την χώρας φαίνεται παρακάτω:

Όπως φαίνεται, οι Αλεπούδες έχουν ήδη ένα πρόβλημα, καθώς δεν υπάρχει κανένα μονοπάτι από την πόλη ~1~ στην πόλη ~2~! Έτσι, για οποιαδήποτε τιμή του ~D~, ο Βασιλιάς Gruff δεν χρειάζεται να κλείσει κανέναν δρόμο.