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