📖 Bài giảng & lời giải: đây là Bài tập 6 trong bài giảng Bài 31: Fenwick, Segment Tree trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Một chiếc hộp ban đầu rỗng. Có $q$ thao tác theo thứ tự, mỗi thao tác thuộc một trong ba loại:

• 1 x: bỏ một số $x$ vào hộp;
• 2 x: lấy một số $x$ ra khỏi hộp (nếu trong hộp không có số $x$ nào thì bỏ qua thao tác này);
• 3 k: in ra số nhỏ thứ $k$ trong hộp (các số trùng nhau được tính riêng, tức là nếu xếp mọi số trong hộp tăng dần thì lấy số ở vị trí thứ $k$); nếu hộp có ít hơn $k$ số thì in -1.

Dữ liệu vào

• Dòng 1: số nguyên $q$ ($1 \le q \le 2 \cdot 10^5$).
• $q$ dòng tiếp theo, mỗi dòng là một thao tác dạng 1 x hoặc 2 x ($1 \le x \le 10^6$), hoặc 3 k ($1 \le k \le 2 \cdot 10^5$).

Dữ liệu bảo đảm có ít nhất một thao tác loại 3.

Kết quả

Với mỗi thao tác loại 3, theo đúng thứ tự, in ra kết quả trên một dòng.

Sample Input

7
1 5
1 2
1 5
3 2
2 5
3 2
3 3

Sample Output

5
5
-1