Реалізуйте sqrt-декомпозицію запитів (алгоритм Мо) для знаходження суми елементів на відрізку. (Цю задачу можна прсотіше зробити префіксними сумами, але в навчальних цілях зробимо її іншим методом).

Формат вхідних даних

В першому рядку ціле число \(N\), кількість елементів масиву (\(1 \le N \le 10^5\)).
В другому рядку елементи масиву. (\(1 \le Ai \le 10^5\))
В третьому рядку вводиться число \(K\) - кількість запитів (\(1 \le K \le 3*10^4\))
В кожному з наступних \(K\) рядків міститься по два числа - номера лівого і правого елементів відрізка масиву

Формат вихідних даних

Для кожного запиту виведіть через пробіл - суму елементів на відрізку

Приклад вхідних даних

5
2 2 2 1 5
2
2 3
2 5

Приклад вихідних даних

4 10