Devendra loves the XOR operation very much which is denoted by sign in most of the programming languages. He has a list of numbers and he wants to know the answers of queries. Each query will be denoted by three numbers i.e. .

For query , he has to print the value of the which can be described as given below. As the value of the can be large. So, print it modulus .

Input Format
The first line contains an integer , i.e., the number of the elements in the list. List is numbered from to .
Next line will contain space seperated integers.
Third line will contain a number i.e. number of queries followed by lines each containing integers .

Output Format
Print lines, line will be answer of query. Answer will be 0 in case of P=R.

Constraints

Sample Input

3
1 2 3
2
1 1 3
2 1 3

Sample Output

5
4

Explanation

For first query, it will will be