Шреддер знову задумав підкорити Нью-Йорк — цього разу за допомогою масиву з чисел! Він наказав своїм підлеглим, Бібопу і Рокстеді, навчитися маніпулювати числами за допомогою дивної операції.
Бібоп вибирає два індекси та , a Рокстеді одночасно виконує над ними операцію Шреддера:
Таку операцію можна виконувати довільну кількість разів, у будь-якому порядку.
Тепер Шреддер ставить своїм бовдурам запитань такого вигляду.
Для заданого відрізку [l, r], яку найбільшу суму елементів можна отримати на цьому відрізку, якщо дозволено виконувати скільки завгодно операцій Шреддера над будь-якими елементами масиву?
Допоможіть Бібопу та Рокстеді відповідати на запитання Шреддера.
Зауважте, що операції не змінюють масив між запитами.
У першому рядку задано ціле число — кількість елементів масиву.
У другому рядку задано чисел a_i — елементи масиву.
У третьому рядку задано ціле число — кількість запитань Шреддера.
У наступних рядках задано по два числа та — межі відрізків у запитаннях.
1 \le n, q \le 10^6,
0 \le a_i < 2^{20},
1 \le l \le r \le n.
Для кожного запитання виведіть ціле число — максимально можливу суму на відрізку після застосування операцій.
Приклад