#153Easy

XOR queries

Time: 1 s · Memory: 256 MB

Prefix sums

Statement

You are given $n$ non-negative integers and $q$ queries. For every query find $a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$ , where $\oplus$ is bitwise XOR.

Input format

The first line contains $n$ and $q$ ( $1 \le n, q \le 2 \cdot 10^5$ ). The second line contains $n$ integers ( $0 \le a_i \le 10^9$ ). Each of the next $q$ lines contains a query: two integers $l$ and $r$ ( $1 \le l \le r \le n$ ).

Output format

For every query print one number on a separate line.

Examples

Input

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

Output

Note

XOR works with prefixes too, because $x \oplus x = 0$ : with $p_i = a_1 \oplus \ldots \oplus a_i$ the answer is $p_r \oplus p_{l-1}$ — the common beginning cancels out. XOR plays the role of subtraction.

The first query of the example: $2 \oplus 4 \oplus 5 = 3$ .

Source: CSES, problem 1650.

XOR queries

Time: 1 s · Memory: 256 MB

Prefix sums

Statement

You are given $n$ non-negative integers and $q$ queries. For every query find $a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$ , where $\oplus$ is bitwise XOR.

Input format

Output format

For every query print one number on a separate line.

Examples

Input

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

Output

Note

The first query of the example: $2 \oplus 4 \oplus 5 = 3$ .

Source: CSES, problem 1650.