Müəmmalı qurğu
Bəli, bu baş verdi! İlk konteak! Gəlmələr Yerdə 2010-da olacaqlar! Və onlar mövcud yer texnologiyalarından istifadə etməklə yığılması mümkün olmayan müəmmalı qurğu gətirməyi söz vermişdilər. Yer kürəsinin əksər alimləri belə düşünürlər! Bütün qəzetlər artıq bunun haqqında məqalələr nəşr etmişlər.
Qurğunun girişinə {a_i} ardıcıllığı verilir. Sonra onun üzərində növbəti iki əməliyyat aparılır:
[l; r] intervalını seçirik və elə bütün i-lər üçün a_i ← a_i^2 mod 2010 əməliyyatını yerinə yetiririk ki, l ≤ i ≤ r olsun.
[l; r] intervalını seçirik və elə bütün a_i cəmini tapırıq ki, l ≤ i ≤ r olsun. Qeyd edək ki, cəm 2010 moduluna görə hesablanmır.
Qəribədir, qurğu 50000 ədəddən ibarət çoxluq üzərində 50000-ə qədər göstərilmiş şəkildə əməliyyat apara bilər. İndiyə qədər heç kim bunu edə bilməmişdir!
Lakin Roman gəlmələrə inanmır və hesab edir ki, bu kiminsə birjada milyon dollar qazanması üçün böyük aldatmasıdır. O bunu sübut etmək istəyir. O Sizi qurğunun işini modelləşdirmək üçün tutmuşdur.
a_i verilənlər ardıcıllığına və əməliyyatlar dəstinə görə, gəlmələrin müəmmalı qurğusunun işini modelləşdirən proqram yazın.
Giriş verilənləri
İlk sətir ardıcıllığın n (1 ≤ n ≤ 50 000) uzunluğunu ehtiva edir. İkinci sətir başlanğıc ardıcıllığı ifadə edən n sayda a_i (0 ≤ a_i ≤ 2009) ədədlərini ehtiva edir. Üçüncü sətir əməliyyatların m (1 ≤ m ≤ 50 000) sayını ehtiva edir. Hər m sətrin hər biri əməliyyatı əks etdirir. j-ci əməliyyat onun k_j ('1' – kvadrata yüksəltmə, '2' – cəmi hesablama) tipini əks etdirir və ardınca da iki l_j və r_j (1 ≤ l_j ≤ r_j ≤ n) tam ədədləri verilir.
Çıxış verilənləri
Hər bir ikinci tip əməliyyat üçün ayrı sətirdə cavabı vermək tələb olunur.