Otoci

Πριν από λίγο καιρό ο Mirko ίδρυσε ένα νέο τουριστικό γραφείο με το όνομα "Dreams of Ice". Το πρακτορείο αγόρασε ~N~ παγωμένα νησιά κοντά στο Νότιο Πόλο και τώρα προσφέρει εκδρομές. Ιδιαίτερα δημοφιλείς είναι ο αυτοκράτορες πιγκουίνοι, που μπορούν να βρεθούν σε μεγάλους αριθμούς στα νησιά.

Το πρακτορείο του Mirko έχει γίνει τεράστια επιτυχία, τόσο μεγάλο που δεν είναι πλέον οικονομικά αποδοτικό να χρησιμοποιεί σκάφη για τις εκδρομές. Το πρακτορείο θα κατασκευάσει γέφυρες μεταξύ των νησιών και θα μεταφέρει τουρίστες με λεωφορεία. Ο Mirko θέλει να εισαγάγει ένα πρόγραμμα υπολογιστή για τη διαχείριση της διαδικασίας κατασκευής γέφυρας έτσι ώστε να γίνονται λιγότερα λάθη.

Τα νησιά αριθμούνται από το ~1~ έως το ~N~. Δεν υπάρχουν δύο νησιά που συνδέονται αρχικά με γέφυρες. Ο αρχικός αριθμός των πιγκουίνων σε κάθε νησί είναι γνωστός. Αυτός ο αριθμός μπορεί να αλλάξει, αλλά θα είναι πάντα μεταξύ ~0~ και ~1\,000~.

Το πρόγραμμά σας πρέπει να χειρίζεται τους ακόλουθους τρεις τύπους εντολών:

• "bridge ~A~ ~B~" – ελήφθη προσφορά για την κατασκευή γέφυρας μεταξύ των νησιών ~A~ και ~B~ (~A~ και ~B~ θα είναι διαφορετικοί). Για να περιορίσετε το κόστος, το πρόγραμμά σας πρέπει να αποδεχτεί την προσφορά μόνο εάν δεν υπάρχει ήδη τρόπος για να φτάσετε από το ένα νησί στο άλλο χρησιμοποιώντας γέφυρες που είχαν κατασκευαστεί στο παρελθόν. Εάν η προσφορά γίνει αποδεκτή, το πρόγραμμα θα πρέπει να εκτυπώσει "yes", μετά το οποίο κατασκευάζεται η γέφυρα. Εάν η προσφορά απορριφθεί, το πρόγραμμα θα πρέπει να εκτυπώνει "no".
• "penguins ~A~ ~X~" – οι πιγκουίνοι στο νησί ~A~ έχουν επαναμετρηθει και υπάρχουν τώρα ~X~ από αυτούς. Αυτή είναι μια ενημερωτική εντολή και το πρόγραμμά σας δεν χρειάζεται να ανταποκριθεί.
• "excursion ~A~ ~B~" - μια ομάδα τουριστών θέλει μια εκδρομή από το νησί ~A~ στο νησί ~B~. Εάν η εκδρομή είναι δυνατή (είναι δυνατή η μετάβαση από το νησί ~A~ στο ~B~), το πρόγραμμα θα πρέπει να εκυπώνει τον συνολικό αριθμό πιγκουίνων που θα έβλεπαν οι τουρίστες στην εκδρομή (συμπεριλαμβανομένων των νησιών ~A~ και ~B~). Διαφορετικά, το πρόγραμμά σας θα πρέπει να βγάζει "impossible".

Σημαντική σημείωση: το πρόγραμμά σας πρέπει να δίνει απαντήσεις στις εντολές "bridge" και "excursion" αμέσως μετά την παραλαβή τους. Το πρόγραμμα του διακομιστή δεν θα στείλει την επόμενη εντολή μέχρι το δικό σας πρόγραμμα ανταποκριθεί στην προηγούμενη.

Μια άλλη σημαντική σημείωση: για να μπορεί το πρόγραμμα του διακομιστή να διαβάζει τις απαντήσεις του προγράμματός σας, το δικό σας πρόγραμμα πρέπει να ξεπλένει την τυπική έξοδο μετά από κάθε απόκριση που βγάζει.

• Στη C++, χρησιμοποιήστε την εντολή cout << flush;
• Στη C, χρησιμοποιήστε flush(stdout);
• Στην pascal, χρησιμοποιήστε flush(output);

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο αριθμό ~N~ ~(1 \le N \le 30\,000)~, τον αριθμό των νησιών.
Η δεύτερη γραμμή περιέχει ~N~ ακέραιους μεταξύ ~0~ και ~1\,000~, τον αρχικό αριθμό πιγκουίνων σε καθένα από τα νησιά.
Η τρίτη γραμμή περιέχει έναν ακέραιο αριθμό ~Q~ ~(1 \le Q \le 300\,000)~, τον αριθμό των εντολών.
Ακολουθούν οι εντολές ~Q~, η καθεμία στη δική της γραμμή. Όπως σημειώθηκε παραπάνω, αφού λάβετε μια εντολή "bridge" ή "εκδρομή", το πρόγραμμά σας δεν θα λάβει άλλη εντολή μέχρι να απαντήσει στην προηγούμενη.

Έξοδος

Εκτυπώστε τις απαντήσεις στις εντολές "bridge" και "excursion", η καθεμία στη δική της γραμμή.

Βαθμολογία

Σε αρχεία ελέγχου αξίας ~50~% των πόντων, η εντολή "penguins" δεν θα εμφανίζεται. Σε αυτά τα αρχεία ελέγχου το ~N~ θα να είναι περιττός, ενώ σε όλες τις άλλες περιπτώσεις το ~N~ θα είναι άρτιος.

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

input

5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5

output

4
impossible
yes
6
yes
yes
15
yes
15
16

input

6
1 2 3 4 5 6
10
bridge 1 2
bridge 2 3
bridge 4 5
excursion 1 3
excursion 1 5
bridge 3 4
excursion 1 5
penguins 3 10
excursion 1 3
bridge 1 5

output

yes
yes
yes
6
impossible
yes
15
13
no