Next#686
Implement a data structure that supports a set of integers, with which it is allowed to perform the following operations:
add() – add to the set the number (if it already exists there, the set is not changed);
next() – print the minimum element of the set that is no less than . If such an element does not exist in the structure, print -1.
The set is initially empty. The first line contains the number of operations (1 \leq n \leq 300\ 000). The next lines contain the operations. Each operation has a type either "+ " or "? ". The operation "? " gives the query next().
If the operation "+ " is executed at the start or after another operation +, it specifies the operation add(). If the operation goes after the query ? with result , then the operation add((i+y) \bmod 10^9) is executed.
In all queries and add operations, the parameters lie in the range from to 10^9.
For each query, print one number—the answer to it.
Example 1