D. Следующий

Реализуйте множество целых чисел с двумя операциями: добавить число и найти наименьший элемент множества, не меньший заданного. Если такого нет, выведите $-1$.

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

Встроенными структурами пользоваться нельзя.

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

На каждый запрос ? выведите ответ в отдельной строке.