Maximizing the Function

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.

Input Format

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 .

Constraints

Subtask

and for of the maximum score
, and for of the maximum score

Output Format

Print lines where line contains the answer to query (i.e., the maximum value of if no more than bits are changed).

Sample Input

Sample Output

4
0

Explanation

Given , we perform the following queries:

If we change to , then we get and .
In this query, .