Sum insertion P83997

Please implement an efficient data structure to support just one operation. Let $x_1, \dots, 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 + \sum_{i \le k \le j} x_k) \bmod 10^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 \le m \le 10^5$, $0 \le y < 10^9$, and $1 \le i \le j \le 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.