\begin{problem}{И снова сумма...}{sum2.in}{sum2.out}{3 секунды}{256 мегабайт}

Реализуйте структуру данных, которая поддерживает
множество $S$ целых чисел, с котором разрешается производить 
следующие операции:
\begin{itemize}
\item $add(i)$ --- добавить в множество $S$ число $i$ (если он
там уже есть, то множество не меняется);
\item $sum(l, r)$ --- вывести сумму всех элементов $x$ из $S$, которые
удовлетворяют неравенству $l \le x \le r$.
\end{itemize}

\InputFile

Исходно множество $S$ пусто. Первая строка входного файла содержит
$n$ --- количество операций ($1 \le n \le 300\,000$). 
Следующие $n$ строк содержат операции.
Каждая операция имеет вид либо <<\t{+ $i$}>>, либо <<\t{? $l$ $r$}>>.
Операция <<\t{? $l$ $r$}>> задает запрос $sum(l, r)$.

Если операция <<\t{+ $i$}>> идет во входном файле в начале или
после другой операции <<\t{+}>>, то она задает операцию $add(i)$.
Если же она идет после запроса <<\t{?}>>, и результат
этого запроса был $y$, то выполняется операция $add((i + y) \bmod 10^9)$.

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

\OutputFile

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

\Example

\begin{example}
\exmp{
6
+ 1
+ 3
+ 3
? 2 4
+ 1
? 2 4
}{
3
7
}%
\end{example}


\end{problem}
