Республиканская олимпиада по информатике 2009 года за 11 класс | Казахстанские олимпиады

Задача B. Фокус

Помните про фокус с мухами, который изобрел Баха? Жома решил посоревноваться с ним и придумал свой фокус! У Жомы есть ящик. Он может запускать туда муху или выпускать. Также, он как хороший дрессировщик знает возраст каждой мухи в минутах с момента ее рождения. А фокус заключается вот в чем: в любой момент он может назвать возраст $K$-й по старшинству мухи, которая находится в ящике среди мух с возрастом от $A$ до $B$ включительно. Попробуйте и вы сделать этот фокус!

Формат входного файла

Первая строка входного файла содержит число $N$ — общее количество событий ($1 \le N \le 2 \cdot 10^5$). Далее следует $N$ строк, каждая из которых описывает одно из событий:

Формат выходного файла

Выходной файл должен содержать такое же количество строк, сколько запросов возраста было во входном файле. Для каждого такого запроса нужно вывести строку, содержащую соответствующее число — ответ на запрос. При этом, если при количество мух с возрастом от $A$ до $B$ в ящике меньше $K$, то нужно вывести $0$.

Примеры

Вход

8
+ 2
+ 3
+ 2
? 2 2 3
- 2
? 2 2 3
- 2
? 2 2 3

Выход

2
3
0