Giải bài trực tuyến

Để đề phòng ruồi tấn công đất nước, nhà vua đã thuê hẳn một chuyên gia về ruồi. Có một cái hộp để nghiên cứu, các con ruồi sẽ bay ra và bay vào chiếc hộp này. Chuyên gia này biết được độ tuổi của từng con ruồi (tính theo phút). Tại mỗi thời điểm, chuyên gia có thể nêu ra tuổi của con ruồi thứ K trong cái hộp trong số các con ruồi có độ tuổi từ A đến B.

Hãy lập trình thực hiện công việc tương tự để nhà vua khỏi mất tiền thuê vị chuyên gia này!

Dữ liệu

Dòng đầu tiên chứa một số nguyên N (1 ≤ N ≤ 2.10⁵) là số lượng sự kiện. N dòng sau, mỗi dòng mô tả một sự kiện:

• + X - một con ruồi có độ tuổi X bay vào hộp
• - X - một con ruồi có độ tuổi X bay ra khỏi hộp
• ? K A B - hỏi tuổi của con ruồi thứ K trong hộp trong số các con ruồi có độ tuổi từ A đến B (1 ≤ K ≤ 10⁵, A ≤ B).

Các số X, A, B nằm trong phạm vi từ 1 đến 10⁹.

Kết quả

Với mỗi câu truy vấn hỏi tuổi, trả về kết quả tương ứng trên một dòng. Nếu số các con ruồi có độ tuổi từ A đến B nhỏ hơn K, in ra 0.

Ví dụ

Dữ liệu
8			
+ 2		
+ 3		
+ 2		
? 2 2 3
- 2		
? 2 2 3
- 2		
? 2 2 3

Output:
2
3
0

Nguồn: 5-й этап Республиканской олимпиады по информатике, 10-11 класс Республика Казахстан, Апрель, 2009