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

У всіх запитах та операціях додавання параметри лежать в інтервалі від 0 до 109.

Вихідні дані

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