Ο Οδυσσέας γύρισε στην Ιθάκη και είναι η ώρα να παίξει το γνωστό παιχνίδι με τους φίλους του. Κάθε ένας από αυτούς πετάει ένα ακόντιο σε μία γραμμή και αυτό καλύπτει ένα διάστημα [i, j] πάνω σε αυτή. Μετά η Πηνελόπη πετάει ένα βέλος και όποιου το ακόντιο είναι πάνω πάνω στο σημείο που πέσει το βέλος, κερδίζει. Κάποιοι παίκτες κάποια στιγμή βαριούνται και αποχωρούν. Μπορείτε να βρείτε ποιος κερδίζει σε κάθε γύρο;
Σας δίνονται M (0 < Μ < 10^6) γεγονότα, που μπορεί να είναι οποιοδήποτε από τα παρακάτω:
- 1 i j: έρχεται ένα καινούργιο ακόντιο που καλύπτει το [i, j]
- 2 i: το i-οστό ακόντιο στην σειρά αφαιρέθηκε, γιατί ο παίκτης που το έριξε αποχώρησε
- 3 i: Η Πηνελόπη έριξε το βέλος στην θέση i. Πρέπει να απαντήσετε ποιο παικτης κέρδισε (δηλαδή σε ποιο ακόντιο έπεσε. Τα ακόντια ξεκινάνε από το 1)
Για κάθε φορά που ρίχνει η Πηνελόπη το βέλος (γεγονός 3) να απαντήσετε ποιος κερδίζει (ποιο ακόντιο είναι πάνω πάνω στην θέση αυτή). Άμα δεν κερδίζει κάποιος τότε να τυπώσετε -1.
Subtask 1 (10 pts)
- 0 < i, j <= 10^2 και 0 < Μ <= 10^5
Subtask 2 (10 pts)
- 0 < i, j <= 10^5 και 0 < Μ <= 5*10^3
Subtask 3 (40 pts)
- 0 < i, j <= 10^5 και 0 < Μ <= 3*10^5
- Δεν υπάρχουν removals
Subtask 4 (40 pts)
- 0 < i, j < 10^5 και 0 < Μ <= 3*10^5
7 1 2 5 3 3 1 4 7 3 4 2 2 3 4 3 8
1 2 1 -1