- Prepare
- Algorithms
- Bit Manipulation
- Maximizing the Function

# Maximizing the Function

# 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**

```
3 2
0 0 1
0 2 1
0 1 0
```

**Sample Output**

```
4
0
```

**Explanation**

Given , we perform the following queries:

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