Və yenə də cəmi... (Asan)#5284
Tam ədədlərdən ibarət S çoxluğunu dəstəkləyən bir məlumat strukturu yaradın və aşağıdakı əməliyyatları yerinə yetirin:
add(i) - S çoxluğuna i ədədini əlavə edin (əgər artıq varsa, çoxluq dəyişməz);
sum(l, r) - S çoxluğunda l ≤ x ≤ r şərtini ödəyən bütün x elementlərinin cəmini hesablayın.
Başlanğıcda S çoxluğu boşdur. Giriş faylının ilk sətiri n - əməliyyatların sayını (1 ≤ n ≤ 100) göstərir. Sonrakı n sətir əməliyyatları təsvir edir. Hər bir əməliyyat ya "+ i", ya da "? l r" formasındadır. "? l r" əməliyyatı sum(l, r) sorğusunu ifadə edir.
Əgər "+ i" əməliyyatı giriş faylında ilk və ya başqa bir "+" əməliyyatından sonra gəlirsə, bu add(i) əməliyyatını ifadə edir. Əgər o, "?" sorğusundan sonra gəlirsə və bu sorğunun nəticəsi y olarsa, add((i + y) mod 10^9) əməliyyatı icra olunur.
Bütün sorğularda və əlavə əməliyyatlarında parametrlər 0 ilə 10^9 arasında yerləşir.
Hər bir sorğu üçün bir ədəd çıxarın - sorğunun cavabı.
Nümunə 1