J. Сколько в диапазоне, без права заглянуть вперёд

Поддерживается мультимножество целых чисел, изначально пустое. Две операции: добавить число и узнать, сколько чисел множества лежит в заданном диапазоне.

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

В первой строке $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$.

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