Please implement an efficient data structure to support just one operation.
Let x_{1}, …, x_{n} be the current elements (natural numbers) in the data structure,
all different and in increasing order.
Given three parameters y, i, and j,
you must insert z = (y + ∑_{i ≤ k ≤ j} x_{k}) mod10^{9} into your data structure.
Assume that you start with just one element, with value 0.

Input

Input begins consists of several cases.
Each case starts with the number of insertions m.
Follow m triples y i j.
Assume 1 ≤ m ≤ 10^{5},
0 ≤ y < 10^{9},
and 1 ≤ i ≤ j ≤ n.
The end of input is indicated with a special case with m = 0.

Output

For every operation, if z is a new value, insert z and print I z. Otherwise, do not insert z and print R z. Print a line with 10 dashes at the end of each case.

Public test cases

**Input**

4 5 1 1 3 1 1 2 1 2 3 2 3 5 0 1 1 999999999 1 1 1 2 2 999999999 1 2 999999999 1 3 0

**Output**

I 5 I 3 R 5 I 11 ---------- R 0 I 999999999 R 0 I 999999998 I 999999996 ----------

Information

- Author
- Pol Mauri
- Language
- English
- Official solutions
- C++
- User solutions
- C++