Tramvaji

Μια μαγική νύχτα ο Patrick και ο Josip μιλούσαν για τον αριθμό 42 και το νόημα της ζωής. Τους διέκοψε η διάσημη γυναικεία φωνή στο τραμ: Επόμενη στάση, Jordanovac. Ο Patrik και ο Josip αφαιρέθηκαν από αυτή την κοινή πρόταση και άρχισαν να συζητούν:

Patrik: Είναι πολύ μικρή η διαδρομή μεταξύ Joranovac και Maksimir, έτσι δεν είναι;
Josip: Ναι, αλλά η διαδρομή μεταξύ Mašićeva και Kvatrić είναι πολύ μικρότερη.
Patrik: Αλήθεια; Διαφωνώ.
Josip: Αναρωτιέμαι, ποια είναι η συντομότερη διαδρομή μεταξύ όλων των σταθμών;

Η Paula, μια μεγάλη λάτρης των δημόσιων συγκοινωνιών, άκουγε προσεκτικά τη συνομιλία τους. Το πρόβλημα της εύρεσης της συντομότερης διαδρομής την ενδιέφερε τόσο πολύ που έμεινε στο τραμ περισσότερο από όσο σκόπευε απλώς για να ακούσει στη συνομιλία τους.

Σε κάθε στάση (εκτός από την πρώτη, όταν μπήκαν στο τραμ) ένα από τα παρακάτω δύο πράγματα συνέβη:

• Ο Patrick είπε: έχουν περάσει t λεπτά από τότε που μπήκαμε στο τραμ
• Ο Josip είπε: Από το σταθμό y σε αυτόν το σταθμό έχουν περάσει t λεπτά

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

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο ~n~ (~2 \le n \le 1\; 000~), τον αριθμό των σταθμών του τραμ.

Η ~i~-η από τις ακόλουθες ~n - 1~ γραμμές περιέχει τις πληροφορίες για το σταθμό ~i + 1~ σε μία από τις παρακάτω μορφές:

• Patrik ~\mathbf{t_i}~ – Η διάρκεια της διαδρομής μεταξύ του σταθμού 1 και του σταθμού ~i + 1~ είναι ~t_i~ (~1 \le t_i \le 10^9~)
• Josip \(\mathvf{y_i}\) ~\mathbf{t_i}~ – Η διάρκεια της διαδρομής μεταξύ του σταθμού ~y~ και του σταθμού ~i + 1~ είναι ~t_i~ (~y_i < i + 1, 1 \le t_i \le 10^9~)

Κάθε σταθμός θα βρίσκεται σε μία ξεχωριστή θέση.

Έξοδος

Σε μία γραμμή εξάγετε τρεις αριθμούς: ~t~, ~x_1~, ~x_2~, τη διάρκεια της συντομότερης διαδρομής και τους δείκτες του σταθμού αφετηρίας και τέρματος αυτής της διαδρομής.

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

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	12	~t_1 \le 1\; 000~
2	13	Κάθε πρόταση ειπώθηκε από τον Patrik.
3	25	Χωρίς επιπλέον περιορισμούς.

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

1ο

input

4
Patrik 3
Patrik 5
Josip 1 7

output

2 2 3

Επεξήγηση Παραδείματος:
Το τραμ οδήγησε για 3 λεπτά από τον πρώτο στο δεύτερο σταθμό και 5 από τον πρώτο στον τρίτο. Μπορούμε να συμπεράνουμε ότι από το δεύτερο μέχρι τον τρίτο σταθμό χρειάστηκαν 2 λεπτά, η οποία είναι η συντομότερη διαδρομή.

2o

input

2
Josip 1 5

output

5 1 2

3o

input

5
Patrik 4
Josip 2 4
Josip 2 6
Josip 4 2

output

2 3 4

Επεξήγηση Παραδείγματος:
Η διαδρομή μεταξύ του τέταρτου και του πέμπτου σταθμού είναι επίσης 2 λεπτά, αλλά επειδή έχουν μεγαλύτερους δείκτες, μόνο η λύση 2 3 4 γίνεται αποδεκτή.