Sum insertion P83997


Statement
 

pdf   zip

html

Please implement an efficient data structure to support just one operation. Let x1, …, xn 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 + ∑ikj xk) mod109 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 ≤ 105, 0 ≤ y < 109, and 1 ≤ ijn. 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++