І знову сума... (Easy)#5284
Реалізуйте структуру даних, яка підтримує множину цілих чисел, з якою дозволяється виконувати наступні операції:
add(i) - додати у множину число (якщо воно там вже є, то множина не змінюється);
sum(l, r) - вивести суму усіх елементів з , які задовольняють нерівності l \leq x \leq r.
Спочатку множина порожня. Перший рядок вхідного файлу містить - кількість операцій (1 \leq n \leq 100). Наступні рядків містять операції. Кожна операція має вигляд або "+ i", або "? l r". Операція "? l r" задає запит sum(l, r).
Якщо операція "+ i" йде у вхідному файлі на початку або після іншої операції "+", то вона задає операцію add(i). Якщо ж вона йде після запиту "?", і результат цього запиту був , то виконується операція \text{add}((i + y) \bmod 10^9).
У всіх запитах та операціях додавання параметри лежать в інтервалі від до 10^9.
Для кожного запиту виведіть одне число - відповідь на запит.
Приклад 1