Barking Dogs!

Ζεις σε μια γειτονιά με σκυλιά. Στα σκυλιά αρέσουν τα σκυλιά. Στα σκυλιά αρέσει ακόμα περισσότερο να γαβγίζουν. Αλλά το καλύτερο από όλα, στα σκυλιά αρέσει να γαβγίζουν όταν άλλα σκυλιά γαβγίζουν.

Κάθε σκύλος έχει μια συλλογή από σκύλους που μπορούν να τον/την ακούσουν. Κάθε σκύλος έχει ένα χρόνο καθυστέρησης στο γάβγισμα αν ακούσει άλλο σκύλο να γαβγίζει.

Ο σκύλος ~1~ αρχίζει πάντα να γαβγίζει πρώτος και αυτό το πρώτο γάβγισμα εμφανίζεται κατά το δευτερόλεπτο ~0~. Η δουλειά σας είναι να υπολογίσετε πόσες φορές έχει γαυγίσει κάθε σκύλος στα πρώτα ~T~ δευτερόλεπτα (κλειστό διάστημα).

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

Κάθε σκύλος ξοδεύει κάθε δευτερόλεπτο κάνοντας ένα από τα τρία πράγματα: κοιμάται, περιμένει ή γαβγίζει. Αν ο σκύλος ~i~ ακούσει ένα γάβγισμα κατά τη διάρκεια ενός δευτερολέπτου ~n~ όταν κοιμάται, ο σκύλος ξυπνά και περιμένει για τα δευτερόλεπτα ~n + 1~ έως ~n + w_i - 1~ (κλειστό διάστημα), γαβγίζει κατά τη διάρκεια του δευτερολέπτου ~n + w_i~ και μετά ξανακοιμάται από το δευτερόλεπτο ~n + wi + 1~ και μετά. Εάν ένας σκύλος ακούσει ένα γάβγισμα κατά τη διάρκεια ενός δευτερολέπτου κατά το οποίο περιμένει ή γαβγίζει, αγνοεί το γαύγισμα.

Κατά τη διάρκεια του δευτερολέπτου ~0~, όλα τα σκυλιά εκτός από το σκυλί ~1~ κοιμούνται.

Είσοδος

Η πρώτη γραμμή της εισόδου είναι το ~D~ (~1 \le D \le 1\,000~), ο αριθμός των σκύλων στη γειτονιά.

Οι επόμενες ~D~ γραμμές καθεμία περιέχουν έναν ακέραιο ~w_i~ (~1 \le w_i \le 1\,000~) που αντιπροσωπεύει τον χρόνο (σε δευτερόλεπτα) που ο σκύλος ~i~ περιμένει πριν σκεφτεί να γαυγίσει αφού άκουσε ένα γαύγισμα.

Η επόμενη γραμμή περιέχει τον αριθμό ~F~ (~1 \le F \le 10\,000~). Σε κάθε μία από τις επόμενες ~F~ γραμμές, υπάρχουν δύο ακέραιοι: το ~i~ και το ~j~, που αντιπροσωπεύουν ότι όταν ένας σκύλος ~i~ γαυγίσει, ο σκύλος ~j~ ακούει αυτό το γαύγισμα. Δεν ισχύει ποτέ ~i = j~.

Η επόμενη γραμμή (η οποία είναι η τελευταία γραμμή της εισόδου) περιέχει τον ακέραιο ~T~ (~1 \le T \le 1\,000~), τον αριθμό των δευτερολέπτων κατά τον οποίο το πρόγραμμά σας θα πρέπει να παρακολουθεί τα σκυλιά.

Έξοδος

Παράξτε μία γραμμή εξόδου για κάθε σκύλο με τη σειρά από τον σκύλο ~1~ στον σκύλο ~D~. Στη γραμμή ~i~, εκτυπώστε τον αριθμό των δευτερολέπτων μεταξύ του κλειστού διαστήματος [~1~, ~T~] που ο σκύλος ~i~ ξόδεψε γαυγίζοντας.

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

input

3
1
1
3
3
1 2
2 3
3 1
10

output

3
2
2

input

3
3
1
3
3
1 2
2 3
3 1
10

output

2
2
1