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

Limits: 2 sec., 512 MiB

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

Бібоп вибирає два індекси \(i\) та \(j\), a Рокстеді одночасно виконує над ними операцію Шреддера: \[a_i = a_i \ \text{ AND } \ a_j, \qquad a_j = a_i \ \text{ OR } \ a_j.\]

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

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

• Для заданого відрізку \([l, r]\), яку найбільшу суму елементів можна отримати на цьому відрізку, якщо дозволено виконувати скільки завгодно операцій Шреддера над будь-якими елементами масиву?

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

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

Input

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

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

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

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

Output

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

Constraints

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

\(0 \le a_i < 2^{20}\),

\(1 \le l \le r \le n\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 1 4 2 3 4 1 1 1 2 1 3 1 4	7 10 10 10