И снова сумма...

Input

Изначально множество $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 включительно.

Output

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

Examples