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.


The set S initially is empty. The first line contains the number of operations n (1n300 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 109) is executed.

In all queries and add operations the parameters lie in the range from 0 to 109.


For each query print one number - the answer to it.

Time limit 1 second
Memory limit 128 MiB
Input example #1
+ 1
+ 3
+ 3
? 2
+ 1
? 4
Output example #1
Author В.Гольдштейн
Source Зимние сборы в Харькове 2010 День 2