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