Республиканская олимпиада по информатике 2009 год

(Сиқыр)

Ограничение по времени:

2 секунд

Ограничение по памяти:

256 мегабайт

Баханың шыбындармен ойлап таплап сиқыры есіңізде ме? Жома онымен жарысуды ұйғарып, өз сиқырын ойлап тапты. Жомада жәшік бар. Ол онда шыбынды кіргізе немесе шығара алады. Сонымен қатар, ол жақсы жаттықтырушы ретінде әр шыбынның туғаннан бастап өмір жасын әр минутына дейін біледі. Сиқыр сипаттамасы: уақыттың әр сәтінде ол жәшіктегі жасы $A$-дан $B$-ға (шеткі мәндерді қоса) дейнгі шыбындардың ішінен жасының үлкендігіне қарай $K$-ші болатын шыбынның жасын айтып бере алады. Сіз де осындай сиқыр жасап көріңіз!

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

Енгізу файлының бірінші жолында $N$ — оқиғалардың жалпы саны ($1 \le N \le 2 \cdot 10^5$). Әрі қарай N жол берілген, әрқайсысы оқиғалардың бірін сипаттайды:

• \t{+ X} — жәшікке жасы $X$ болатын шыбынды кіргізді;
• \t{- X} — жәшіктен жасы $X$ болатын шыбынды шығарды;
• \t{? K A B} — сиқыршыдан жәшіктегі жасы $A$-дан $B$-ға дейнгі шыбындардың ішінен жасының үлкендігіне қарай $K$-ші болатын шыбынның жасын сұрады ($1 \le K \le 10^5$, $A \le B$).

Шыбынның жасы ($X$, $A$, $B$) — $1$-ден $10^5$-ге дейінгі бүтін сан.

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

Шығыс файлда саны — енгізу файлдағы жас шамасы туралы сұраныстардың санындай болатын жолдар болуы тиіс. Әрбір осындай сұраныс үшін сәйкесінше санды — сұранысқа жауапты құрайтын жолды шығару керек. Егер жәшіктегі жасы $A$-дан $B$-ға дейнгі шыбындардың саны $K$-дан кіші болса, онда $0$-ді шығару керек.

Пример:

Вход

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

Ответ

2
3
0