Interval Collection

Η Altina ξεκινά μια συλλογή διαστημάτων. Ένα διάστημα ορίζεται ως δύο θετικοί ακέραιοι [~l~, ~r~] τέτοιοι ώστε ~l~ ~<~ ~r~. Λέμε ότι το μήκος αυτού του διαστήματος είναι ~r~ - ~l~. Επιπλέον, λέμε ότι ένα σύνολο [~l~, ~r~] περιέχει ένα άλλο σύνολο [~x~, ~y~] αν ~l~ ~\le~ ~x~ και ~y~ ~\le~ ~r~. Συγκεκριμένα, κάθε διάστημα περιέχει τον εαυτό του.

Για ένα μη κενό σύνολο ~S~ διαστημάτων, ορίζουμε το σύνολο κοινών διαστημάτων ως όλα τα διαστήματα [~x~, ~y~] που περιέχονται σε κάθε διάστημα [~l~, ~r~] στο ~S~. Εάν το σύνολο των κοινών διαστημάτων δεν είναι κενό, τότε λέμε ότι το μεγαλύτερο κοινό διάστημα του ~S~ είναι ίσο με το κοινό διάστημα με το μεγαλύτερο μήκος.

Για το ίδιο σύνολο ~S~, ορίζουμε το σύνολο των εσωκλειόμενων διαστημάτων ως όλα τα διαστήματα [~x~, ~y~] που περιέχουν κάθε διάστημα [~l~, ~r~] στο ~S~. Σημειώστε ότι αυτό το σύνολο είναι πάντα μη κενό, οπότε λέμε ότι το μικρότερο εσωκελιόμενο διάστημα του ~S~ είναι ίσο με το εσωκελειόμενο διάστημα με το μικρότερο μήκος.

Αρχικά, η Altina δεν διαθέτει διαστήματα στη συλλογή της. Υπάρχουν ~Q~ συμβάντα που αλλάζουν το σύνολο των διαστημάτων που έχει στη συλλογή της.

Ο πρώτος τύπος συμβάντος είναι όταν η Altina προσθέτει ένα διάστημα [~l~, ~r~] στη συλλογή της. Σημειώστε ότι αυτό το διάστημα θα μπορούσε να έχει το ίδιο [~l~, ~r~] με ένα άλλο διάστημα στη συλλογή της. Θα πρέπει να αντιμετωπίζονται ως ξεχωριστά διαστήματα.

Ο δεύτερος τύπος συμβάντος είναι όταν η Altina αφαιρεί ένα υπάρχον διάστημα [~l~, ~r~] από τη συλλογή της. Σημειώστε ότι αν η Altina έχει περισσότερα από ένα διαστήματα με το ίδιο [~l~, ~r~], αφαιρεί ακριβώς ένα από αυτά.

Μετά από κάθε συμβάν, η Altina επιλέγει ένα μη κενό υποσύνολο ~S~ διαστημάτων που κατέχει στη συλλογή της που πληρεί τις ακόλουθες προϋποθέσεις:

• Από όλα τα σετ ~S~ που θα μπορούσε να επιλέξει η Altina, επιλέγει ένα που δεν έχει μεγαλύτερο κοινό διάστημα, αν είναι δυνατόν. Αν αυτό είναι αδύνατο, τότε επιλέγει ένα που έχει το μήκος του μεγαλύτερου κοινού διαστήματος όσο το δυνατόν μικρότερο.

• Από όλα τα σετ ~S~ που ικανοποιούν την προηγούμενη συνθήκη, επιλέγει ένα που έχει το μήκος του μικρότερου εσωκελιόμενου διαστήματος όσο το δυνατόν μικρότερο.

Η δουλειά σας είναι να προσδιορίσετε το μήκος του ελάχιστου εσωκλειόμενου διαστήματος του συνόλου ~S~ που επέλεξε η Altina μετά από κάθε συμβάν.

Είσοδος

Η πρώτη γραμμή της εισόδου περιέχει ~Q~ (~1~ ~\le~ ~Q~ ~\le~ ~500\,000~), τον συνολικό αριθμό πράξεων πρόσθεσης και αφαίρεσης. Οι επόμενες ~Q~ γραμμές είναι σε μία από τις παρακάτω μορφές:

• ~A~ ~l~ ~r~: πρόσθεσε το διάστημα [~l~, ~r~] στη συλλογή της Altina.

• ~R~ ~l~ ~r~: αφαίρεσε ένα από τα διαστήματα [~l~, ~r~] από τη συλλογή της Altina. Είναι εγγυημένο ότι το διάστημα που θα αφαιρεθεί υπάρχει και ότι η συλλογή δεν θα είναι κενή αφού αφαιρεθεί το διάστημα.

Για όλα τα υποπροβλήματα, ~1~ ~\le~ ~l~ ~<~ ~r~ ~\le~ ~1\,000\,000~.

Βαθμολογία

Για ~3~ από τους ~25~ διαθέσιμους βαθμούς, ~Q~ ~\le~ ~500~.

Για επιπλέον ~8~ από τους ~25~ διαθέσιμους βαθμούς. ~Q~ ~\le~ ~12\,000~.

Για επιπλέον ~7~ από τους ~25~ διαθέσιμους βαθμούς. ~Q~ ~\le~ ~50\,000~.

Για επιπλέον ~4~ από τους ~25~ διαθέσιμους βαθμούς, η ακόλουθη προϋπόθεση ισχύει μετά από κάθε συμβάν: για κάθε δύο ξεχωριστά διαστήματα [~l_1~, ~r_1~] και [~l_2~, ~r_2~] στη συλλογή της Altina, είτε ~r_1~ ~<~ ~l_2~ ή ~r_2~ ~<~ ~l_1~.

Έξοδος

Η έξοδος αποτελείται από ~Q~ γραμμές, με κάθε γραμμή να περιέχει το μήκος του ελάχιστου εσωκλειόμενου διαστήματος για την επιλογή του ~S~ της Altina όπως περιγράφεται στην περιγραφή του προβλήματος.

Παράδειγμα

input

5
A 1 5
A 2 7
A 4 6
A 6 8
R 4 6

output

4
6
5
4
7

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

Αφού προσθέσουμε το διάστημα [~1~, ~5~], υπάρχει μόνο ένα διάστημα, οπότε ~S~ = {|~1~, ~5~|} είναι η μόνη έγκυρη επιλογή και το ελάχιστο εσωκλειόμενο διάστημα είναι το [~1~, ~5~].

Αφού προσθέσουμε το διάστημα [~2~, ~7~], ~S~ = {|~1~, ~5~|, |~2~, ~7~|} και το μεγαλύτερο κοινό διάστημα είναι το [~2~, ~5~] και το ελάχιατο εσωκλειόμενο διάστημα το [~1~, ~7~].

Αφού προσθέσουμε το διάστημα [~4~, ~6~], ~S~ = {|~1~, ~5~|, |~4~, ~6~|} και το μεγαλύτερο κοινό διάστημα είναι το [~4~, ~5~] και το ελάχιατο εσωκλειόμενο διάστημα το [~1~, ~6~].

Αφού προσθέσουμε το διάστημα [~6~, ~8~], ~S~ = {|~4~, ~6~|, |~6~, ~8~|}, δεν έχει μεγαλύτερο κοινό διάστημα και το ελάχιατο εσωκλειόμενο διάστημα το [~4~, ~8~]. Σημειώστε ότι ~S~ = {|~1~, ~5~|, |~6~, ~8~|} επίσης δεν έχει μεγαλύτερο κοινό διάστημα αλλά το ελάχιστο εσωκλειόμενο διάστημα [~1~, ~8~] έχει μεγαλύτερο μήκος από το [~4~, ~8~].

Αφού αφαιρεθεί το διάστημα [~4~,~6~], ~S~ = {|~1~, ~5~|, |~6~, ~8~|}, δεν έχει μεγαλύτερο κοινό διάστημα και ελάχιστο εσωκλειόμενο διάστημα το [~1~, ~8~].