And again the sum...#2310
Implement a data structure to manage a set of integers, supporting the following operations:
: Add the integer to the set . If is already in the set, no changes are made.
\text{sum}(l, r): Calculate and return the sum of all elements in that satisfy l \leq x \leq r.
Initially, the set is empty. The first line contains the integer (1 \leq n \leq 300\ 000), representing the number of operations. The following lines each contain an operation in one of the following forms:
"+ i"
"? l r"
The operation "? l r" corresponds to the query \text{sum}(l, r).
If a "+ i" operation is the first operation or follows another "+" operation, it corresponds to . However, if it follows a "?" query, and the result of that query was , then the operation becomes \text{add}((i + y) \bmod 10^9).
All parameters in the queries and add operations are within and 10^9 inclusive.
For each query operation, output a single number, which is the result of the query.
Example 1