І знову сума...
Реалізуйте структуру даних, яка підтримує множину S цілих чисел, з якою дозволяється виконувати наступні операції:
add(i) - додати у множину S число i (якщо воно там вже є, то множина не змінюється);
sum(l, r) - вивести суму усіх елементів x з S, які задовольняють нерівності l ≤ x ≤ r.
Вхідні дані
Спочатку множина S порожня. Перший рядок містить кількість операцій n (1 ≤ n ≤ 300000). Наступні n рядків містять операції. Кожна операція має вигляд або "+ i", або "? l r". Операція "? l r" задає запит sum(l, r).
Якщо операція "+ i" йде на початку або після іншої операції "+", то вона задає операцію add(i). Якщо ж вона йде після запиту "?", і результат цього запиту був y, то виконується операція add((i + y) mod 10^9).
У всіх запитах та операціях додавання параметри лежать в інтервалі від 0 до 10^9.
Вихідні дані
Для кожного запиту виведіть одне число - відповідь на запит.