Следующий
Реалізуйте структуру даних, яка підтримуєт множину S цілих чисел, з якою дозволено виконувати наступні операції:
add(i) – додати у множину S число i (якщо воно там вже є, то множина не змінюється);
next(i) – вивести мінімальний елемент множини, не менший i. Якщо шуканий елемент у структурі відсутній, необхідно вивести –1.
Вхідні дані
Вхідна множина S порожня. Перший рядок вхідного файлу містить n – кількість операцій (1 ≤ n ≤ 300 000). Наступні n рядків містять операції. Кожна операція має вид або "+ i", або "? i". Операція "? i" задає запит next(i).
Якщо операція "+ i" йде у вхідному файлі на початку або після іншої операції "+", то вона задає операцію add(i). Якщо ж вона йде після запиту "?" і результатом цього запиту був y, то виконується операція add((i+y) mod 10^9).
У всіх запитах і операціях додавання параметри лежать в інтервалі від 0 до 10^9.
Вихідні дані
Для кожного запиту виведіть одне число – відповідь на запит.