И снова сумма... (Easy)
Реализуйте структуру данных, которая поддерживает множество S целых чисел, с которой разрешается производить следующие операции:
add(i) - добавить в множество S число i (если оно там уже есть, то множество не меняется);
sum(l, r) - вывести сумму всех элементов x из S, которые удовлетворяют неравенству l ≤ x ≤ r.
Входные данные
Исходно множество S пусто. Первая строка входного файла содержит n - количество операций (1 ≤ n ≤ 100). Следующие n строк содержат операции. Каждая операция имеет вид либо "+ i", либо "? l r". Операция "? l r" задает запросsum(l, r).
Если операция "+ i" идет во входном файле в начале или после другой операции "+", то она задает операцию add(i). Если же она идет после запроса "?", и результат этого запроса был y, то выполняется операция add((i + y) mod 10^9).
Во всех запросах и операциях добавления параметры лежат в интервале от 0 до 10^9.
Выходные данные
Для каждого запроса выведите одно число - ответ на запрос.