For an array of positive integers of length , we define as follows:
Let initially a variable be equal to ;
For one coin, it is allowed to increase the value of by ;
For one coin, it is allowed to choose an element of the array () and replace it with , where denotes the operation of bitwise exclusive OR;
equals the minimum number of coins needed to make all elements of the array simultaneously equal to zero.
The bitwise exclusive OR of non-negative integers and equals a non-negative integer, in which in the binary representation, there is a one at a certain position only if in the binary representations of and at this position there are different values. For example, .
An array of positive integers of length and queries of the form , are given. For each query, it is necessary to find .
You need to implement the following functions:
void init(integer n, array of integers a)
--- an integer representing the length of the array;
--- an array of integers of length ;
this function does not return anything.
integer ask(integer l, integer r)
--- an integer representing the left boundary of the query;
--- an integer representing the right boundary of the query;
this function returns an integer --- .
array of integers askAll(integer q, array of integers l, array of integers r)
--- an integer representing the number of queries;
--- an array of integers of length ; represents the left boundary of the -th query;
--- an array of integers of length ; represents the right boundary of the -th query;
this function returns an array of integers; the -th number should be equal to the answer to the -th query.
输入格式
The first line contains three integers , , and (; ) --- the number of numbers, the number of queries, and the format of the queries, respectively.
The second line contains integers () --- the elements of the array .
The next lines contain two integers and () --- the parameters of the -th query.
The function will be called exactly once.
If , then the function with all queries will be called exactly once. If , then the function will be called exactly times.
输出格式
The grader will output integers in separate lines --- the answers to the queries.
