To-Do List

Ουάου, η λίστα εργασιών σας είναι άδεια... αλλά όχι για πολύ! Τα επόμενα δευτερόλεπτα, θα πρέπει να διαχειριστείτε ~Q~ ενημερώσεις στη λίστα εργασιών σας.

Για τον πρώτο τύπο ενημέρωσης, πρέπει να προσθέσετε μια νέα εργασία για το σπίτι στη λίστα εργασιών σας. Αυτή η εργασία θα γίνει διαθέσιμη στην αρχή του δευτερολέπτου ~s~ και θα χρειαστεί ~t~ δευτερόλεπτα για να ολοκληρωθεί (~1 \le s,t \le 10^6~). Για τον δεύτερο τύπο ενημέρωσης, πρέπει να αφαιρέσετε την ~i~-οστή εργασία για το σπίτι που προστέθηκε στη λίστα εργασιών σας.

Μετά από κάθε ενημέρωση, αναρωτιέστε: ποια είναι η νωρίτερη χρονική στιγμή κατά την οποία μπορείτε να ολοκληρώσετε όλες τις εργασίες για το σπίτι που βρίσκονται στη λίστα εργασιών σας;

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

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει έναν ακέραιο ~Q~.

Οι επόμενες ~Q~ γραμμές περιέχουν από μία ενημέρωση, η οποία ξεκινά με έναν χαρακτήρα A ή D.

Μια γραμμή που ξεκινά με A αντιστοιχεί στον πρώτο τύπο ενημέρωσης και τελειώνει με δύο κρυπτογραφημένους* ακεραίους ~s'~ και ~t'~.

Μια γραμμή που ξεκινά με D αντιστοιχεί στον δεύτερο τύπο ενημέρωσης και τελειώνει με έναν κρυπτογραφημένο ακέραιο ~i'~. Εγγυάται ότι έχουν προστεθεί τουλάχιστον ~i~ εργασίες και ότι η ~i~-οστή εργασία που προστέθηκε δεν έχει αφαιρεθεί ακόμη.

Εγγυάται ότι υπάρχει τουλάχιστον μία εργασία για το σπίτι στη λίστα εργασιών μετά από κάθε ενημέρωση.

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι διαθέσιμοι ~15~ βαθμοί:

Βαθμοί	Όρια του ~Q~	Επιπλέον Περιορισμοί
~2~	~1 \le Q \le 3000~	Κανένας
~6~	~1 \le Q \le 10^6~	Μόνο ενημερώσεις του πρώτου τύπου
~7~	~1 \le Q \le 10^6~	Κανένας

*Σημείωση: η είσοδος για αυτό το πρόβλημα είναι κρυπτογραφημένη. Για να αποκρυπτογραφήσετε και να λάβετε τις πραγματικές τιμές των ~s~, ~t~ και ~i~, μπορείτε να χρησιμοποιήσετε τους παρακάτω τύπους:

~s = (s' + ans) \bmod (10^6 + 3)~

~t = (t' + ans) \bmod (10^6 + 3)~

~i = (i' + ans) \bmod (10^6 + 3)~

Εδώ, το ~ans~ αντιπροσωπεύει την απάντηση μετά την προηγούμενη ενημέρωση και αρχικά είναι ~0~, πριν από οποιαδήποτε ενημέρωση.

Μπορεί επίσης να σας φανεί χρήσιμο να γνωρίζετε ότι το mod αντιστοιχεί στον τελεστή % στις περισσότερες γλώσσες προγραμματισμού και δηλώνει το υπόλοιπο μετά τη διαίρεση. Για παράδειγμα, ~5 \bmod 3 = 2~ και ~17 \bmod 4 = 1~.

Έξοδος

Εκτυπώστε ~Q~ γραμμές, όπου η ~i~-οστή γραμμή περιέχει την νωρίτερη χρονική στιγμή, σε δευτερόλεπτα, κατά την οποία μπορείτε να ολοκληρώσετε όλες τις εργασίες για το σπίτι που βρίσκονται στη λίστα εργασιών σας μετά την ~i~-οστή ενημέρωση.

input

6
A 3 3
A 2 0
A 999996 999995
D 999991
A 1000000 999994
D 999992

output

5
11
13
11
13
9

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

Η μη κρυπτογραφημένη είσοδος του παραδείγματος παρέχεται για διευκόλυνση αναφοράς.

input

6
A 3 3
A 7 5
A 4 3
D 1
A 8 2
D 2

output

5
11
13
11
13
9

Μετά την πρώτη ενημέρωση, μπορούμε να ξεκινήσουμε την πρώτη εργασία στην αρχή του δευτερολέπτου ~3~ και να την ολοκληρώσουμε στο τέλος του δευτερολέπτου ~5~ (διάστημα ~[3,5]~).

Μετά τη δεύτερη ενημέρωση, μπορούμε να εκτελέσουμε την πρώτη εργασία στο διάστημα ~[3,5]~ και τη δεύτερη εργασία στο διάστημα ~[7,11]~.

Μετά την τρίτη ενημέρωση, μπορούμε να εκτελέσουμε την πρώτη εργασία στο διάστημα ~[3,5]~, την τρίτη εργασία στο διάστημα ~[6,8]~ και, στη συνέχεια, τη δεύτερη εργασία στο διάστημα ~[9,13]~.

Μετά την τέταρτη ενημέρωση, μπορούμε να εκτελέσουμε την τρίτη εργασία στο διάστημα ~[4,6]~ και τη δεύτερη εργασία στο διάστημα ~[7,11]~.

Μετά την πέμπτη ενημέρωση, μπορούμε να εκτελέσουμε την τρίτη εργασία στο διάστημα ~[4,6]~, τη δεύτερη εργασία στο διάστημα ~[7,11]~ και την τέταρτη εργασία στο διάστημα ~[12,13]~.

Μετά την έκτη ενημέρωση, μπορούμε να εκτελέσουμε την τρίτη εργασία στο διάστημα ~[4,6]~ και την τέταρτη εργασία στο διάστημα ~[8,9]~.

input

2
A 1000000 1000000
A 4 4

output

1999999
2999999

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

Η μη κρυπτογραφημένη είσοδος είναι:

2
A 1000000 1000000
A 1000000 1000000

Μετά την πρώτη ενημέρωση, η εργασία είναι διαθέσιμη στην αρχή του δευτερολέπτου ~1.000.000~ και χρειάζεται ~1.000.000~ δευτερόλεπτα για να ολοκληρωθεί, οπότε ολοκληρώνεται στο τέλος του δευτερολέπτου ~1.999.999~.

Μετά τη δεύτερη ενημέρωση, η δεύτερη εργασία είναι επίσης διαθέσιμη στην αρχή του δευτερολέπτου ~1.000.000~ και χρειάζεται ~1.000.000~ δευτερόλεπτα. Επομένως, αφού οι δύο εργασίες πρέπει να εκτελεστούν διαδοχικά, η δεύτερη ολοκληρώνεται στο τέλος του δευτερολέπτου ~2.999.999~.