Stogovi

Ο Μίρκο παίζει με στοίβες. Στην αρχή του παιχνιδιού, έχει μια κενή στοίβα που δηλώνεται με τον αριθμό 0. Στο ~i~-οστό βήμα του παιχνιδιού θα επιλέξει μια υπάρχουσα στοίβα που συμβολίζεται με ~v~, θα την αντιγράψει και θα κάνει μία από τις παρακάτω ενέργειες:

  ~a~. τοποθετεί τον αριθμό ~i~ πάνω από τη νέα στοίβα

  ~b~. αφαιρέστε τον αριθμό από την κορυφή της νέας στοίβας

  ~c~. επιλέξτε μια άλλη στοίβα που συμβολίζεται με ~w~ και μετρήστε πόσοι διαφορετικοί αριθμοί υπάρχουν στη νέα στοίβα
   και στη στοίβα που συμβολίζεται με ~w~

Η νεα στοίβα που δημιουργήθηκε συμβολίζεται με ~i~.

Του Mirko δεν του αρέσει να εργάζεται με στοίβες, επομένως θέλει να γράψετε ένα πρόγραμμα που θα το κάνει για αυτόν. Για κάθε λειτουργία τύπου ~b~ τυπώστε τον αριθμό που αφαιρείται από τη στοίβα και για κάθε λειτουργία τύπου ~c~ μετρήστε τους απαιτούμενους αριθμούς και τυπώστε πόσοι από αυτούς υπάρχουν.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~N\;(1 \leq N \leq 300\,000)~, τον αριθμό των βημάτων στο παιχνίδι του Mirko. Τα βήματα του παιχνιδιού σημειώνονται χρονολογικά με τους πρώτους \(Ν\) ακέραιους αριθμούς. Η ~i~-οστή από τις ακόλουθες ~N~ γραμμές περιέχει την περιγραφή του ~i~-οστού βήματος του παιχνιδιού σε μία από τις ακόλουθες τρεις μορφές:

• "a v" για λειτουργία τύπου ~a~.
• "b v" για λειτουργία τύπου ~b~.
• "c v w" για λειτουργία τύπου ~c~.

Ο πρώτος χαρακτήρας στη γραμμή υποδηλώνει τον τύπο της λειτουργίας και ο επόμενος ένας ή δύο υποδηλώνουν τις συνοδευτικές ετικέτες στοίβας που θα είναι πάντα ακέραιοι από το διάστημα ~[0,\;i - 1]~.

Για κάθε λειτουργία του τύπου ~b~, η στοίβα από την οποία αφαιρούμε το στοιχείο δεν θα είναι κενή.

Έξοδος

Για κάθε λειτουργία τύπου ~b~ ή ~c ~ τυπώστε τον απαιτούμενο αριθμό, η καθεμία στη δική της γραμμή, με τη σειρά που δόθηκαν οι λειτουργία στην είσοδο.

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

input

5
a 0
a 1
b 2
c 2 3
b 4

output

2
1
2

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

Στην αρχή, έχουμε τη στοίβα ~S_0 = \{\}~. Στο πρώτο βήμα, αντιγράφουμε το ~S_0~ και τοποθετούμε τον αριθμό 1 από πάνω, άρα ~S_1 = \{1\}~. Στο δεύτερο βήμα, αντιγράφουμε το ~S_1~ και τοποθετούμε το 2 από πάνω του, ~S_2 = \{1,\;2\}~. Στο τρίτο βήμα αντιγράφουμε το ~S_2~ και αφαιρούμε τον αριθμό 2 από αυτό, ~S_3 = \{1\}~. Στο τέταρτο βήμα αντιγράφουμε ~S_2~ και συμβολίζουμε το αντίγραφο με ~S_4~, μετά μετράμε τους αριθμούς που εμφανίζονται στη νέα στοίβα ~S_4~ και στοίβα ~S_3~, ο μόνος τέτοιος αριθμός είναι ο αριθμός 1 οπότε η λύση είναι 1. Στο πέμπτο βήμα αντιγράφουμε το ~S_4~ και αφαιρούμε τον αριθμό 2 από αυτό, ~S_5 = \{1\}~.

input

11
a 0
a 1
a 2
a 3
a 2
c 4 5
a 5
a 6
c 8 7
b 8
b 8

output

2
2
8
8