Džumbus

Ο Marin είναι καλός άνθρωπος, επομένως θα οργανώσει ~Q~ πάρτι για τους ~N~ φίλους του, οι οποίοι είναι όλοι ανταγωνιστικοί προγραμματιστές. Το μόνο ποτό που θα σερβιριστεί στα πάρτι του θα είναι το džumbus — ένα μείγμα από κόλα και χυμό τζίντζερ.

Για κάθε φίλο του, ο Marin γνωρίζει την ποσότητα džumbus που χρειάζεται να πιει για να χαλαρώσει. Γνωρίζει επίσης ότι υπάρχουν ~M~ ζευγάρια ανθρώπων μεταξύ των φίλων του, έτσι ώστε, αν και οι δύο είναι χαλαροί, θα αρχίσουν να ανταλλάσσουν λύσεις προηγούμενων προβλημάτων COCI (αφού δεν υπάρχουν δημοσιευμένα editorials). Όταν ένα άτομο ~A~ μοιράζεται τις λύσεις του με το άτομο ~B~, το άτομο ~B~ μπορεί να αποφασίσει να μοιραστεί αυτές τις λύσεις με τον ίδιο τρόπο, αλλά είναι επίσης γνωστό ότι τα ζεύγη Μ σχηματίζονται με τρόπο που είναι αδύνατο αυτές οι λύσεις να επανέλθουν στο πρόσωπο ~A~ κατά τη διάρκεια αυτού του πάρτι, ανεξάρτητα από τη σειρά με την οποία έγιναν οι ανταλλαγές.

Η Marin έχει ετοιμάσει διαφορετικές ποσότητες džumbus για κάθε πάρτι. Κατά τη διάρκεια κάθε πάρτι, θα μοιράζει το ποτό με τρόπο που να μεγιστοποιεί τον αριθμό των ατόμων που θα ανταλλάξουν τουλάχιστον μία φορά τις λύσεις τους με άλλο άτομο σε αυτό το πάρτι.

Το καθήκον σας είναι να προσδιορίσετε τον αριθμό των ατόμων που θα ανταλλάξουν τις λύσεις τους για καθένα από τα πάρτι ~Q~.

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~N~ και ~M~ από την περιγραφή της εργασίας.
Η δεύτερη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~D_i~, χωρισμένους στο διάστημα, τις ποσότητες džumbus που χρειάζονται για να χαλαρώσουν οι φίλοι του Marin, που δίνονται με σειρά από έναν φίλο αριθμό 1 σε έναν φίλο αριθμό ~N~.
Η i-οστή των επόμενων ~M~ γραμμών περιέχει δύο ακέραιους ~A_i~ και ~B_i\;(A_i \ne B_i)~, που δηλώνουν ένα ζευγάρι φίλων από την περιγραφή της εργασίας.
Η επόμενη γραμμή περιέχει έναν ακέραιο ~Q~ από την περιγραφή της εργασίας.
Οι επόμενες γραμμές ~Q~ περιέχουν έναν μόνο ακέραιο ~S_i~ που αντιπροσωπεύει τη συνολική ποσότητα džumbus που πρόκειται να σερβιριστεί στο i-οστό party.

Έξοδος

Καταχωρίστε τον αριθμό των ατόμων που θα ανταλλάξουν τις λύσεις τους για καθένα από τα πάρτι ~Q~. Η απάντηση για κάθε πάρτι πρέπει να δίνεται σε ξεχωριστή γραμμή. Σημειώστε ότι τα πάρτι είναι ανεξάρτητα μεταξύ τους.

Βαθμολογία

Σε όλα τα υποπροβλήματα, ισχύει ~0 \le M < N \le 1000,\;1 \le Q \le 2 \cdot 10^5,\;1 \le D_i \le 10^9~ και ~1 \le S_i \le 10^9~.

Υποπρόβλημα	Βαθμοί	Περιορισμοί
		~M = N - 1,\;1 \le S_i \le 1000~
1	20	Οι φίλοι του Marin θα ζευγαρωθούν με τρόπο που κάθε φίλος θα ανταλλάσσει τις λύσεις του με το πολύ δύο άλλα άτομα. ~M = N - 1~
2	30	Οι φίλοι του Marin θα ζευγαρωθούν με τρόπο που κάθε φίλος θα ανταλλάσσει τις λύσεις του με το πολύ δύο άλλα άτομα.
3	30	~N \le 100~
5	30	Κανένας επιπλέον περιορισμός.

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

input

1 0
1000
1
1000

output

0

input

3 2
1 2 3
1 2
1 3
3
2
3
5

output

0
2
2

input

14 13
2 3 4 19 20 21 5 22 6 7 23 8 10 14
1 2
1 3
1 4
2 5
2 6
3 7
3 8
3 9
4 10
8 11
10 13
10 12
12 14
3
45
44
23

output

8
7
5

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

Στο πρώτο πάρτι, ο Marin αποφάσισε να χαλαρώσει τους φίλους του με τους δείκτες ~1, 2, 3, 7, 9, 10, 12~ και ~13~. Έχουν πιει συνολικά 45 μονάδες džumbus.