Və yenə də kədər...
Verilənlər strukturunu həyata keçirin ki, bu struktur tam ədədlər çoxluğu S-i dəstəkləsin və aşağıdakı əməliyyatları yerinə yetirməyə imkan versin:
add(i) - S çoxluğuna i ədədini əlavə et (əgər artıq oradadırsa, çoxluq dəyişməz);
sum(l, r) - S çoxluğundakı x elementlərinin cəmini hesabla, burada l ≤ x ≤ r qeyri-bərabərliyi təmin olunur.
Giriş məlumatları
Əvvəlcə S çoxluğu boşdur. İlk sətir əməliyyatların sayını n (1 ≤ n ≤ 300000) ehtiva edir. Növbəti n sətir əməliyyatları ehtiva edir. Hər bir əməliyyat ya "+ i", ya da "? l r" formasındadır. "? l r" əməliyyatı sum(l, r) sorğusunu təyin edir.
Əgər "+ i" əməliyyatı əvvəlində və ya başqa bir "+" əməliyyatından sonra gəlirsə, o zaman add(i) əməliyyatını təyin edir. Əgər o, "?" sorğusundan sonra gəlirsə və bu sorğunun nəticəsi y idisə, o zaman add((i + y) mod 10^9) əməliyyatı yerinə yetirilir.
Bütün sorğularda və əlavə əməliyyatlarında parametrlər 0 ilə 10^9 arasında yerləşir.
Çıxış məlumatları
Hər bir sorğu üçün bir ədəd çıxarın - sorğunun cavabı.