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

Реализуйте множество целых чисел с двумя операциями: добавить число и посчитать сумму всех чисел множества, лежащих в отрезке $[l, r]$. Повторное добавление уже имеющегося числа множество не меняет.

Запросы приходят онлайн: если операция добавления идёт сразу после запроса, ответ на который был $y$, то добавляется не $i$, а $(i + y) \bmod 10^9$.

В первой строке — число операций $n$ ($1 \le n \le 3 \cdot 10^5$). В следующих $n$ строках — операции вида + i или ? l r. Все параметры целые, от $0$ до $10^9$.

На каждый запрос ? выведите сумму чисел множества в отрезке $[l, r]$.