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

\(add(k)\) - додати в множину \(S\) число \(k\) (якщо воно там вже є, то множина не змінюється);
\(next(k)\) - вивести мінімальний елемент множини, не менший за \(k\). Якщо такий елемент відсутній в структурі, необхідно вивести -1.

Формат вхідних даних

Спочатку множина \(S\) пуста.
Перший рядок містить ціле число \(N\) - кількість операцій (\(1 \le N \le 300000\)). Наступні \(N\) рядків містять операції. Кожна операція має вигляд або "+ k ", або "? k ". Операція "? k " позначає запит \(next(k)\) .

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

В усіх запитах та операціях додавання параметри знаходяться в інтервалі від \(0\) до \(10^9\)

Формат вихідних даних

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

Приклад вхідних даних

6
+ 1
+ 3
+ 3
? 2
+ 1
? 4

Приклад вихідних даних

3
4