Limits 1s, 512 MB

Bit operators perform bit-wise operations between two binary numbers.

Wikipedia says, binary operations are...

... fast, simple and directly supported by the processor, and is used to manipulate values for comparisons and calculations. On simple low-cost processors, typically, bit-wise operations are substantially faster than division, several times faster than multiplication, and sometimes significantly faster than addition. While modern processors usually perform addition and multiplication just as fast as bit-wise operations due to their longer instruction pipelines and other architectural design choices, bit-wise operations do commonly use less power because of the reduced use of resources.

Three most commonly used bit-wise operators are AND, OR and XOR. These operators are so common that popular languages like C++ provides built-in support for them.

Saif is interested in building an operating system. He needs to make many bit-wise operations on an array of numbers to make his calculations faster. So he decides to work with you on making a smart query handler that would perform fast bit-wise operations on a large collection of numbers.

You will be given an array A, index x and index y of that array and a bit-wise operator. You have to perform the bit-wise operation on that array from index x to y. For example, if your operator is OR you will have to perform:

A[x] OR A[x+1] OR A[x+2] OR .... A[y]

Please note that when x is equal to y, the above sequence of operations will only have one term.

Saif is an exceptional programmer and you do not want to miss out on working with him in this project of his.

Input

The first line contains an integer N (1 ≤ N ≤ 105), the number of elements in the array. The next line contains N integers Ai (1 ≤ Ai ≤ 109), where each number is the ith element of the array in given order.

The next line contains an integer Q (1 ≤ Q ≤ 105), the number of queries that you need to process. The next Q lines will be in the following format:

{x} {operator} {y}

Here x and y (1 ≤ x ≤ y ≤ N) are the starting index and ending index of the array respectively. The operator is either OR, XOR, or AND.

Output

For each query, output a single line containing the answer of the given query. The ith line of the output would contain the answer of the ith query. Please see the samples for the exact formatting.

Samples

InputOutput
5
1 2 3 4 5
3
1 AND 2
1 OR 2
1 XOR 2
0
3
3
InputOutput
5
1 2 3 4 5
3
1 OR 1
1 AND 2
1 XOR 3
1
0
0

If you are not familiar with bit-wise operators, here are few tips:

Let's say you have two 1-bit numbers X and Y. Thus, X and Y can only hold 0 or 1 as their values. The table below shows the result of applying each of the operator on different values of X and Y.

XYOperatorResult
00AND0
01AND0
10AND0
11AND1
00OR0
01OR1
10OR1
11OR1
00XOR0
01XOR1
10XOR1
11XOR0

Submit

Login to submit.

Statistics

73% Solution Ratio
Sopto008Earliest, Dec '16
SadikMRFastest, 0.0s
SadikMRLightest, 5.4 kB
SadikMRShortest, 728B
Toph uses cookies. By continuing you agree to our Cookie Policy.