Bebop, Rocksteady, and Shredder's Operation

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Shredder has once again plotted to conquer New York — this time using an array of \(n\) numbers! He ordered his minions, Bebop and Rocksteady, to learn how to manipulate the numbers using a strange operation.

Bebop chooses two indices \(i\) and \(j\), and Rocksteady simultaneously performs the Shredder’s operation on them: \[a_i = a_i \ \text{ AND } \ a_j, \qquad a_j = a_i \ \text{ OR } \ a_j.\]

This operation can be performed an arbitrary number of times, in any order.

Now Shredder asks his goons \(q\) questions of the following form.

• For a given segment \([l, r]\), what is the maximum sum of elements that can be obtained on this segment, if they are allowed to perform any number of Shredder’s operations on any elements of the array?

Help Bebop and Rocksteady answer Shredder’s questions.

Note that operations do not modify the array between queries.

Input

The first line contains an integer \(n\) — the number of elements in the array.

The second line contains \(n\) numbers \(a_i\) — the elements of the array.

The third line contains an integer \(q\) — the number of Shredder’s questions.

The next \(q\) lines each contain two numbers \(l\) and \(r\) — the boundaries of the segments in the queries.

Output

For each query, output an integer — the maximum possible sum on the segment after applying the operations.

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