Реалізуйте структуру даних, що підтримує безліч \(S\) цілих чисел, з яким дозволяється робити наступні операції:

• \(add(i)\) --- додати до безлічі \(S\) число \(i\) (якщо він там вже є, то безліч не змінюється);
• \(sum(l, r)\) --- вивести суму всіх елементів \(x\) з \(S\), які задовольняють нерівності \(l \le x \le r\).

Формат вхідних даних

На початку множина \(S\) порожня.

Перший рядок вхідного файлу містить \(n\) --- кількість операцій (\(1 \le n \le 300\,000\)).

Наступні \(n\) рядків містять операції. Кожна операція має вигляд або + \(i\), або ? \(l\) \(r\). Операція ? \(l\) \(r\) запитує \(sum(l, r)\).

Якщо операція + \(i\) йде у вхідному файлі на початку або після іншої операції +, вона задає операцію \(add(i)\). Якщо вона йде після запиту ?, і результат цього запиту був \(y\), виконується операція \(add((i + y) \bmod 10^9)\).

У всіх запитах та операціях додавання параметри лежать в інтервалі від \(0\) до \(10^9\).

Формат вихідних даних

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

Приклад вхідних даних

6
+ 1
+ 3
+ 3
? 2 4
+ 1
? 2 4

Приклад вихідних даних

3
7