Своппер
Gömrükdən keçməzdən əvvəl Aaz və Skiv səfər zamanı əldə etdikləri gəlirləri bəyan etməli idilər. Bu, olduqca böyük bir rəqəm ardıcıllığı ilə nəticələndi və onun işlənməsi xeyli vaxt apardı.
– Svopper əyri, - gömrük işçisi işi başa düşən kimi dedi.
– Svopper nədir? - Skiv maraqla soruşdu.
Aaz izah etdi ki, svopper məlumat strukturu olub, aşağıdakıları edə bilir:
x-dən y-ə qədər olan cüt uzunluqlu bir seqment götürüb, x ilə x + 1, x + 2 ilə x + 3 və s. yerlərini dəyişmək;
a-dan b-ə qədər istənilən seqmentin cəmini hesablamaq.
Hesablama uzun müddət çəkə biləcəyini nəzərə alaraq, “MİF” korporasiyası sizdən svopper problemini həll etməyi və bunu effektiv şəkildə modelləşdirməyi xahiş etdi.
Giriş məlumatları
Bir və ya bir neçə testdən ibarətdir. Hər bir testin ilk sətirində ardıcıllığın uzunluğu n və əməliyyatların sayı m (1 ≤ n, m ≤ 100000) verilir. Testin ikinci sətiri modulu 10^6-dan çox olmayan n tam ədədi ehtiva edir - ardıcıllığın özü. Daha sonra m sətir gəlir - 1 x[i] y[i] - birinci tip sorğu və 2 a[i] b[i] - ikinci tip sorğu formatında. Bütün n və m cəmi bütün məlumatlar üzrə 200000-i keçmir. Giriş məlumatları iki sıfırdan ibarət sətirlə tamamlanır. Zəmanət verilir ki, x[i] < y[i], a[i] ≤ b[i].
Çıxış məlumatları
Hər bir test üçün ikinci tip sorğuların cavablarını nümunədə göstərildiyi kimi verin. Testlərin cavablarını boş sətirlə ayırın.