Sansa's Escape

3

5 votes
Easy
Problem

As you all know, Sansa is trying to escape from the Boltons' specially from Ramsey!

Winterfell is divided in an straight line of ice. In the line, each block has some thickness value. Ramsey would catch Sansa and Theon in an interval of ice if the XOR of all thickness of ice in that interval is greater than some value.

Well I am a fan of Ramsey, so you will be given Q queries, each having 2 integers a and b. You have to give the XOR of thickness of all ices in the interval between a (inclusive) and b (inclusive).

Input Format

First Line contains N denoting size of winterfell on a straight line.

Next line contains N space separated integers indicating thickness of ice.

Next line contains Q indicating the number of queries.

Next Q lines contain two space separated integers a and b as mentioned above.

Output Format

Q lines - each contatining an integer for the required query.

Constrains

1 <= N, Q <= 100000

0 <= a <= b <= N-1

Winterfell follow 0 based indexing, that is a and b range from 0 to N-1

Author : Manish Berwani

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

GOT

Editor Image

?