Consider an array of binary integers (i.e., 's and 's) defined as .
Let be the bitwise XOR of all elements in the inclusive range between index and index in array . In other words, . Next, we'll define another function, :
Given array and independent queries, perform each query on and print the result on a new line. A query consists of three integers, , , and , and you must find the maximum possible you can get by changing at most elements in the array from to or from to .
Note: Each query is independent and considered separately from all other queries, so changes made in one query have no effect on the other queries.
The first line contains two space-separated integers denoting the respective values of (the number of elements in array ) and (the number of queries).
The second line contains space-separated integers where element corresponds to array element .
Each line of the subsequent lines contains space-separated integers, , and respectively, describing query .
- and for of the maximum score
- , and for of the maximum score
Print lines where line contains the answer to query (i.e., the maximum value of if no more than bits are changed).
3 2 0 0 1 0 2 1 0 1 0
Given , we perform the following queries:
- If we change to , then we get and .
- In this query, .