eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Следующий

Следующий

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Реалізуйте структуру даних, яка підтримуєт множину S цілих чисел, з якою дозволено виконувати наступні операції:

  • add(i) – додати у множину S число i (якщо воно там вже є, то множина не змінюється);

  • next(i) – вивести мінімальний елемент множини, не менший i. Якщо шуканий елемент у структурі відсутній, необхідно вивести –1.

Вхідні дані

Вхідна множина S порожня. Перший рядок вхідного файлу містить n – кількість операцій (1n300 000). Наступні n рядків містять операції. Кожна операція має вид або "+ i", або "? i". Операція "? i" задає запит next(i).

Якщо операція "+ i" йде у вхідному файлі на початку або після іншої операції "+", то вона задає операцію add(i). Якщо ж вона йде після запиту "?" і результатом цього запиту був y, то виконується операція add((i+y) mod 10^9).

У всіх запитах і операціях додавання параметри лежать в інтервалі від 0 до 10^9.

Вихідні дані

Для кожного запиту виведіть одне число – відповідь на запит.

Приклад

Вхідні дані #1
6
+ 1
+ 3
+ 3
? 2
+ 1
? 4
Вихідні дані #1
3
4
Автор В.Гольдштейн
Джерело Зимние сборы в Харькове 2010 День 2