Реалізуйте структуру даних, яка підтримує множину \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 Для кожного запиту виведіть одне число - відповідь на запит.