Бібоп, Рокстеді і операція Шреддера#12987

Бібоп, Рокстеді і операція Шреддера

2 секунди
512 мегабайтів
Середня

Шреддер знову задумав підкорити Нью-Йорк — цього разу за допомогою масиву з чисел! Він наказав своїм підлеглим, Бібопу і Рокстеді, навчитися маніпулювати числами за допомогою дивної операції.

Бібоп вибирає два індекси та , a Рокстеді одночасно виконує над ними операцію Шреддера:

a_i = a_i \ \text{ AND } \ a_j, \qquad a_j = a_i \ \text{ OR } \ a_j.

Таку операцію можна виконувати довільну кількість разів, у будь-якому порядку.

Тепер Шреддер ставить своїм бовдурам запитань такого вигляду.

Допоможіть Бібопу та Рокстеді відповідати на запитання Шреддера.

Зауважте, що операції не змінюють масив між запитами.

Вхідні дані

У першому рядку задано ціле число — кількість елементів масиву.

У другому рядку задано чисел a_i — елементи масиву.

У третьому рядку задано ціле число — кількість запитань Шреддера.

У наступних рядках задано по два числа та — межі відрізків у запитаннях.

1 \le n, q \le 10^6,

0 \le a_i < 2^{20},

1 \le l \le r \le n.

Вихідні дані

Для кожного запитання виведіть ціле число — максимально можливу суму на відрізку після застосування операцій.

Приклади

Приклад

Loading
Loading