C. Poyezd vagonlari

“Toshkent ekspress” poyezdi n ta vagondan iborat. Vagonlar lokomotivdan boshlab 1 dan n gacha raqamlangan, i-vagonda aᵢ ta yo‘lovchi bor.

Poyezd boshlig‘i yo‘l davomida q marta quyidagicha savol beradi: “l-vagondan r-vagongacha (ikkalasi ham kiradi) jami nechta yo‘lovchi ketyapti?” Boshliq juda shoshqaloq, shuning uchun har bir savolga tez javob beradigan dastur yozing.

Kirish ma’lumotlari

Birinchi qatorda ikkita butun son — n va q.
Ikkinchi qatorda n ta butun son — a₁, a₂, …, aₙ.
Keyingi q ta qatorning har birida ikkita butun son — l va r.

Chiqish ma’lumotlari

Har bir so‘rov uchun alohida qatorda aₗ + aₗ₊₁ + … + aᵣ yig‘indini chiqaring.

Cheklovlar

1 ≤ n, q ≤ 2·10⁴; 0 ≤ aᵢ ≤ 10⁹; 1 ≤ l ≤ r ≤ n.

1–70-testlar 1 balldan, 71–80-testlar 3 balldan, jami 100 ball. 1–2-testlar — shartdagi misollar.

1-misol: 1-so‘rov 7 + 0 + 25 = 32; 2-so‘rov — barcha vagonlar, 12 + 7 + 0 + 25 + 3 + 9 = 56; 3-so‘rov — faqat 5-vagon, 3.

2-misolda javob 3 000 000 000 — bu 2³¹ dan katta, e’tibor bering.