TopCoder

Thumb a

User's AC Ratio

95.2% (40/42)

Submission's AC Ratio

39.7% (60/151)

Description

你,妹可,睜開眼睛後發現關於自己的事唯一記得的只有名字。

你從損壞的冷凍艙中爬了出來,周圍都是無機質的儀錶板。
由於一直等待也不是辦法,你決定去尋找一些線索。
經由一些蛛絲馬跡以及你驚人的推理(DP)能力,你很快的知道這裡是硬佛石株式會社的總部,硬佛大樓。
硬佛石株式會社是硬佛帝國最大的企業,也是整個帝國運作的中心。

但是很顯然的你身處在一片廢墟中。

你到處亂走,終於發現了一扇門裡透出了微弱的光。

「這是!」

在你眼前的是一個未損壞的冷凍艙,裡面好像躺了一個人。
身為妹可,看到有人在睡覺當然要叫醒他,於是你到了儀表板前面,儀表板上顯示出ᚳᚤᛤᛘᛰ᛭᛭ᚻ, 看起來很像C/C++11

運用你驚人的推理(DP)能力,你很快的知道供應這個冷凍艙能量的,是一整排的「萌」能量槽,每個能量槽都有一個能量值。
而每經過一段時間,冷凍艙就會對一段區間的能量槽發出一陣擾動,而你只要將那個區間的能量槽進行一種很特別的運算-XOR-就可以得到和諧的共鳴頻率,抵消該次擾動。只要成功抵消所有的擾動,你就能喚醒沉睡在冷凍艙中的人。
也就是說,你只要將該區間全部的數字XOR起來,就可以得到和諧的共鳴頻率。

『在別人睡覺時配合她打呼的頻率這種變態的行為,我才沒有呢!』----妹可。

Input Format

第一行有兩個整數N、Q,代表能量槽的數量和有幾陣擾動。
第二行有N個整數Hi,代表第i個能量槽的「萌」能量值。
接下來Q行每行兩個整數l、r,代表擾動的區間。

你可以假設,
對於33%的測資,滿足N≤50,將區間中的值全部加起來也可以得到答案。
對於66%的測資,滿如N≤100000,Q≤10。
對於100%的測資,滿足N≤1000000,Q≤1000000,0≤hi≤1018 ,1≤l≤r≤N。

Output Format

總共輸出M行。
每行對於每陣擾動輸出一個整數代表和諧的共鳴頻率。

Sample Input

6 3
8 4 2 32 1 16
2 5
1 6
3 6

Sample Output

39
63
51

Hints

在ᚳᚤᛤᛘᛰ᛭᛭ᚻ裡,如果要做XOR運算可以用 ^ 運算子。
附帶一提,XOR運算是符合結合律的喔!
而且 A ^ B ^ B == A 喔!
由於輸入檔龐大,請使用ᚳᚤᛤᛘᛰ᛭᛭ᚻ中較快的輸出入函式。
如果你要用ᚳᚤᛤᛘᛰ᛭᛭ᚻ裡的ᚥᛔᛕ(也許是scanf)輸入ᚧᚧᚩᛗᛉ(大概是long long int )時,請用ᛨᚫᚫᛄ(%lld吧)輸入。

PS.由於那些是古代文字,所以你的電腦可能看不到,可以考慮換個字體XD。

Problem Source

資訊社 28屆C/C++學術考試 by果茶

Subtasks

For Testdata: 0 ~ 2, Score: 33
For Testdata: 3 ~ 5, Score: 33
For Testdata: 6 ~ 8, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536