Implement a data structure that supports a set S of integers with the following operations:
add(i) - add into the set S the number i (if it is already there, the set does not change);
sum(l, r) - print the sum of all elements x from S, which satisfy inequality l ≤ x ≤ r.
Initial set S is empty. Первая строка содержит количество операций n (1 ≤ n ≤ 300000). Следующие n строк содержат операции. Каждая операция имеет вид либо "+ i", либо "? l r". Операция "? l r" задает запрос sum(l, r).
Если операция "+ i" идет в начале или после другой операции "+", то она задает операцию add(i). Если же она идет после запроса "?", и результат этого запроса был y, то выполняется операция add((i + y) mod 10^9
).
Во всех запросах и операциях добавления параметры лежат в интервале от 0 до 10^9
.
Для каждого запроса выведите одно число - ответ на запрос.