e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

И снова сумма...

И снова сумма...

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 lxr.

Input

Initial set S is empty. Первая строка содержит количество операций n (1n300000). Следующие n строк содержат операции. Каждая операция имеет вид либо "**+ i**", либо "**? l r**". Операция "**? l r**" задает запрос sum(l, r).

Если операция "**+ i**" идет в начале или после другой операции "+", то она задает операцию add(i). Если же она идет после запроса "?", и результат этого запроса был y, то выполняется операция add((i + y) mod 109).

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

Output

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

Time limit 3 seconds
Memory limit 128 MiB
Input example #1
6
+ 1
+ 3
+ 3
? 2 4
+ 1
? 2 4
Output example #1
3
7