And again the sum...
Implement a data structure to manage a set S of integers, supporting the following operations:
add(i): Add the integer i to the set S. If i is already in the set, no changes are made.sum(l, r): Calculate and return the sum of all elements x in S that satisfy l ≤ x ≤ r.
Input
Initially, the set S is empty. The first line of input contains the integer n (1 ≤ n ≤ 300,000), representing the number of operations. The following n lines each contain an operation, either in the form "+ i" or "? l r". The operation "? l r" corresponds to the query sum(l, r).
If a "+ i" operation is the first operation or follows another "+" operation, it directly corresponds to add(i). However, if it follows a "?" query, and the result of that query is y, then the operation becomes add((i + y) mod 10^9).
All parameters in the queries and addition operations are within the range from 0 to 10^9.
Output
For each query operation, output a single number, which is the result of the query.