描述

给一个长度为n的整数数组，有q次询问，每次询问下标x到y之间，所有元素的异或值是多少？第一个元素的下标为1。 注意：异或满足交换律。

输入描述

第一行 正整数n和q（n，q≤100000） 第二行 输入n个空格隔开的正整数 以下q行，每行两个整数x和y。

输出描述

输出q行，每行输出下标x到y之间所有元素的异或值。

用例输入 1

6 3

2 3 4 1 5 7

1 2

3 5

3 6

用例输出 1

1

0

7