e-olymp
Məsələlər

Müəmmalı qurğu

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ə {ai} ardıcıllığı verilir. Sonra onun üzərində növbəti iki əməliyyat aparılır:

  1. [l; r] intervalını seçirik və elə bütün i-lər üçün aiai2mod 2010 əməliyyatını yerinə yetiririk ki, lir olsun.
  2. [l; r] intervalını seçirik və elə bütün ai cəmini tapırıq ki, lir 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.

ai 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(1n50 000) uzunluğunu ehtiva edir. İkinci sətir başlanğıc ardıcıllığı ifadə edən n sayda ai(0ai2009) ədədlərini ehtiva edir. Üçüncü sətir əməliyyatların m(1m50 000) sayını ehtiva edir. Hər m sətrin hər biri əməliyyatı əks etdirir.j-ci əməliyyat onun kj('1' – kvadrata yüksəltmə, '2' – cəmi hesablama) tipini əks etdirir və ardınca da iki ljrj(1ljrjn) 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.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
3
17 239 999
4
2 1 3
1 2 3
2 2 3
2 1 2
Çıxış verilənləri #1
1255
1882
858
Müəllif R.Satukov, A.Lopatin
Mənbə ACM ICPC 2009-2010, NEERC, Northern Subregional Contest, St Petersburg, October 17, 2009