“…I always wanted to become an architect, but I’m not very good at math.”
Aishwarya was saying this to her friend Puper. Puper motivated her for screwing up the things related to math and said he will also help her if needed.
Being motivated, she started up practicing hard problems of maths and she got stuck in a problem and asked for help from Puper. She is playing with XOR, given an array (containing only 0 and 1) as element of N length.
Given L and R, she wants to know the value of XOR of all elements from L to R (both inclusive) and number of unset bits (0's) in the given range of the array.
Being new she finds it tough so she ask for help from Puper. Puper also finds it tough and confusing. So he ask for your help.
The first line contains the number N and the next line contains N numbers containing 0 and 1 only. Next line contain number of query q, and next q lines contains L and R.
For each query print the xor value and number of unset bits in that range.
1<=N<=100000 (1-based indexing of elements)
In the given case the bit sequence is of length 5 and the sequence is 1 0 0 0 1. For query 1 the range is 2 4, and the answer is (array xor array xor array) = 0, and number of zeroes are 3, so output is 0 3. Similarly for other queries.