eolymp
Задачи

Следующий

Следующий

Реализуйте структуру данных, которая поддерживает множество 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 109).

Во всех запросах и операциях добавления параметры лежат в интервале от 0 до 109.

Выходные данные

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
6
+ 1
+ 3
+ 3
? 2
+ 1
? 4
Выходные данные #1
3
4
Автор В.Гольдштейн
Источник Зимние сборы в Харькове 2010 День 2