Задача №2782. Следующий
Реализуйте структуру данных, которая поддерживает множество \(S\) целых чисел, с котором разрешается производить следующие операции:
- \(add(i)\) — добавить в множество \(S\) число \(i\) (если он там уже есть, то множество не меняется);
- \(next(i)\) — вывести минимальный элемент множества, не меньший \(i\). Если искомый элемент в структуре отсутствует, необходимо вывести -1.
Исходно множество \(S\) пусто. Первая строка входного файла содержит \(n\) — количество операций (\(1 \le n \le 300\,000\)). Следующие \(n\) строк содержат операции. Каждая операция имеет вид либо «+ \(i\)», либо «? \(i\)». Операция «? \(i\)» задает запрос \(next(i)\).
Если операция «+ \(i\)» идет во входном файле в начале или после другой операции «+», то она задает операцию \(add(i)\). Если же она идет после запроса «?», и результат этого запроса был \(y\), то выполняется операция \(add((i + y) \bmod 10^9)\).
Во всех запросах и операциях добавления параметры лежат в интервале от \(0\) до \(10^9\).
Для каждого запроса выведите одно число — ответ на запрос.
6 + 1 + 3 + 3 ? 2 + 1 ? 4
3 4