І знову сума...

Вхідні дані

Спочатку множина $S$ порожня. У першому рядку знаходиться ціле число $n$ (1 \leq n \leq 300\ 000) — кількість операцій. Наступні $n$ рядків містять одну з операцій у такому форматі:

• "+ i"

• "? l r"

Операція "? l r" відповідає запиту \text{sum}(l, r).

Якщо операція "+ i" є першою або слідує після іншої операції "+", то вона відповідає $\text{add}(i)$. Проте якщо вона слідує після запиту "?", і результат цього запиту був $y$, тоді операція стає \text{add}((i + y) \bmod 10^9).

Усі параметри у запитах і операціях додавання знаходяться у межах від $0$ до 10^9 включно.

Вихідні дані

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

Приклади