M. Сумма в диапазоне, онлайн

Поддерживается мультимножество целых чисел, изначально пустое. Операции: добавить число и узнать сумму чисел множества, лежащих в заданном диапазоне. Все числа в операциях зашифрованы последним выведенным ответом.

В первой строке $q$ ($1 \le q \le 2 \cdot 10^5$). В следующих $q$ строках операции.

Операция + y — добавить число $x = (y + last) \bmod (10^9 + 1)$.

Операция ? y z — вывести сумму чисел множества в диапазоне $[\min(u, v), \max(u, v)]$, где $u = (y + last) \bmod (10^9 + 1)$, $v = (z + last) \bmod (10^9 + 1)$.

Здесь $last$ — последний выведенный ответ, до первого запроса $last = 0$. Числа $y$ и $z$ во вводе — от $0$ до $10^9$.

Для каждой операции второго вида выведите сумму в отдельной строке.