Babbling Brooks

Μια σειρά από ρέματα τρέχουν στην πλαγιά ενός βουνού. Η πλαγιά του βουνού είναι πολύ βραχώδης και έτσι τα ρέματα χωρίζονται και επανενώνονται πολλές φορές. Στους πρόποδες του βουνού αναδύονται αρκετά ρέματα ως ποτάμια. Η δουλειά σας είναι να υπολογίσετε πόσο νερό ρέει σε κάθε ποτάμι.

Σε οποιοδήποτε δεδομένο υψόμετρο υπάρχουν ~n~ ρέματα, με την ένδειξη ~1~ έως ~n~ από αριστερά προς τα δεξιά. Καθώς προχωράμε στην πλαγιά του βουνού, ένα από τα ρέματα μπορεί να χωριστεί σε μια αριστερή διχάλα και μια δεξιά διχάλα, αυξάνοντας τον συνολικό αριθμό των ρεμάτων κατά ~1~ ή δύο ρέματα μπορεί να επανενωθούν, μειώνοντας τον συνολικό αριθμό των ρεμάτων κατά ~1~. Μετά από διάσπαση ή επανένωση, τα ρέματα επαναριθμούνται διαδοχικά από αριστερά προς τα δεξιά. Υπάρχει πάντα τουλάχιστον ένα ρέμα και δεν υπάρχουν ποτέ περισσότερα από ~100~ ρέματα.

Η πρώτη γραμμή εισόδου περιέχει το ~n~, τον αρχικό αριθμό των ρεμάτων σε κάποιο μεγάλο υψόμετρο. Οι επόμενες ~n~ γραμμές δίνουν τη ροή σε κάθε ένα από τα ρέματα, από αριστερά προς τα δεξιά. Προχωρώντας στην πλαγιά του βουνού, συναντώνται πολλές θέσεις διαχωρισμού ή επανένωσης. Για κάθε θέση διαχωρισμού, θα υπάρχουν τρεις γραμμές εισόδου:

• μια γραμμή περιέχει το ~99~ (για να υποδείξει μια διαίρεση)
• μια γραμμή περιέχει τον αριθμό του ρέματος που χωρίζεται
• μια γραμμή περιέχει έναν αριθμό μεταξύ ~0~ και ~100~, το ποσοστό της ροής από το διαχωρισμένο ρέμα, που ρέει στην αριστερή διχάλα. (Το υπόλοιπο ρέει στη δεξιά διχάλα).

Για κάθε θέση ένωσης, θα υπάρχουν δύο γραμμές εισόδου:

• μια γραμμή περιέχει το ~88~ (για να υποδείξει μια ένωση)
• μια γραμμή περιέχει τον αριθμό της ροής που ενώνεται ξανά με τη ροή στα δεξιά της

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

• μια γραμμή που περιέχει το ~77~ (για να υποδείξει το τέλος της εισόδου)

Η δουλειά σας είναι να καθορίσετε πόσα ρέματα αναδύονται στους πρόποδες του βουνού και ποια είναι η ροή στο καθένα. Η έξοδος σας είναι μια ακολουθία πραγματικών αριθμών, στρογγυλοποιημένη στον πλησιέστερο ακέραιο, δίνοντας τη ροή στους ποταμούς από ~1~ έως ~n~.

Παράδειγμα

input

3
10
20
30
99
1
50
88
3
88
2
77

output

5 55