Description

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

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

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

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

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

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

Input Format

$N \ Q$
$a_0 \ a_1 \ a_2 \ ... \ a_n-1$
$q_1l \ q_1r$
$q_2l \ q_2r$
$...$
$q_nl \ q_nr$
其中
$0<N, Q \le 2*10 ^ 6$
$ 0 \le q_il \le q_ir < N$
$a \le 10 ^ 9$

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}$
$18_{10}=1010_2$
$6_{10}=0110_2$
$2_{10}=0010_2$
$0_{10}=0000_2$
全部XOR起來為$1110_2=22_{10}$

a^b

a xor b

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

Subtasks

No. Testdata Range Constraints Score
1 0~9 $0<N, Q \le 1000$ 40
2 0~19 無其他限制 60

TopCoder

lemonilemon
學弟加電研!

User's AC Ratio

70.6% (12/17)

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