Description

在一個隱匿在雲霧之間的幽靈谷,存在著一座神秘的星光寺廟。傳說這裡是神祕能量的聚集之地,擁有與星辰相連的智慧。村莊中的居民們常常在夢中得到神秘的提示,引領他們尋找通往星光寺廟的道路。

有一天,一位年輕的冒險家,艾薩克,決定踏上星光之旅,穿越幽靈谷追尋寺廟的蹤跡。當他抵達星光寺廟時,一道閃耀著星辰光芒的大門在他面前展開,迎接著他的是星光寺廟的守護者,一位身著星光羽衣的神祕長者。

長者告訴艾薩克,星光智慧可以透過數字的奧秘而顯現。為了證明這種智慧的力量,他提供了一場神秘的試煉,要求艾薩克解開一個關於星辰數字的謎題。

謎題如下:星光寺廟的神聖樹上結滿了N閃亮的星辰果實,每顆果實都擁有一種神奇的能量。艾薩克的任務是進行一系列共Q次的查詢,每次選擇兩顆星辰果實l,r之間的範圍,計算該範圍內所有果實([l,r])的 XOR 總和。

為了完成試煉,艾薩克獲得了一塊星辰碎片,它可以連接他的靈魂與星光智慧。當他運用這塊碎片完成一次查詢時,星光寺廟充滿神秘的星辰光芒,彷彿連接著天地之間的奧秘。

通過這場冒險,艾薩克不僅解開了星辰數字的神秘,還獲得了星辰碎片的祝福。星光寺廟成為村莊的傳奇,而艾薩克的冒險故事傳遍整個幽靈谷,激發了更多冒險者尋求星光智慧的奇蹟。從此以後,幽靈谷成為星光的聖地,彷彿在星辰光芒中綻放著無盡的冒險與奇蹟。

Input Format

N Q
a0 a1 a2 ... an1
q1l q1r
q2l q2r
...
qnl qnr
其中
0<N,Q2106
0qilqir<N
a109

Output Format

對於每次詢問輸出該區間所有元素xor的節果

Sample Input 1

10 5
12 2 10 5 12 4 18 6 2 0 
6 9
7 9
0 2
2 4
1 2

Sample Output 1

22
4
4
3
8

Hints

對於第一筆範測的第一筆詢問
[6,9]=18,6,2,0
1810=10102
610=01102
210=00102
010=00002
全部XOR起來為11102=2210

a^b

a xor b

有一個性質
a ^ b ^ b = a

Subtasks

No. Testdata Range Constraints Score
1 0~9 0<N,Q1000 40
2 0~19 無其他限制 60

TopCoder

roychuang
AAAAAA

User's AC Ratio

73.7% (14/19)

Tags

Problem Source

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 65536 1 2
1 2000 65536 65536 1 2
2 2000 65536 65536 1 2
3 2000 65536 65536 1 2
4 2000 65536 65536 1 2
5 2000 65536 65536 1 2
6 2000 65536 65536 1 2
7 2000 65536 65536 1 2
8 2000 65536 65536 1 2
9 2000 65536 65536 1 2
10 2000 65536 65536 2
11 2000 65536 65536 2
12 2000 65536 65536 2
13 2000 65536 65536 2
14 2000 65536 65536 2
15 2000 65536 65536 2
16 2000 65536 65536 2
17 2000 65536 65536 2
18 2000 65536 65536 2
19 2000 65536 65536 2