Kesma yigʻindisi soʻrovlari

Shart

Birinchi qatorda n soni, ikkinchi qatorda n ta butun son berilgan. Uchinchi qatorda soʻrovlar soni q berilgan. Keyingi q ta qatorning har birida l va r sonlari berilgan (1 ≤ l ≤ r ≤ n). Har bir soʻrov uchun a_l dan a_r gacha elementlar yigʻindisini alohida qatorda chiqaring.

Misollar

5
1 2 3 4 5
3
1 3
2 5
3 3

6
14
3

3
-1 -2 -3
2
1 3
2 2

-6
-2

Cheklovlar

• 1 ≤ n, q ≤ 10^5
• -10^9 ≤ a_i ≤ 10^9