User's AC Ratio

100.0% (14/14)

Submission's AC Ratio

32.9% (27/82)

Description

欸藍,你會做資料傳輸校驗嗎?
資料傳輸校驗跟競程到底有什麼關係呢?
很多人會質疑競程的實用性,覺得這些演算法實際上根本用不到
實際上在競程中學習的演算法,大多數都是有實際應用的
例如在 filesystem 中就時常使用二元樹的變形來快速找到檔案
在資料傳輸或儲存時也常用 xor 進行正確性檢查

而藍......根本不會
因為上課根本沒教
藍:欸可是 our 課程沒教怎麼辦
沒用的助教:那就出成題目讓學生教你吧

大家加油
現在有一個序列 $X_1, X_2, \cdots, X_n$
還有詢問 $a$ $b$
代表從 $X_a \oplus X_{a+1} \oplus X_{a+2} \oplus \cdots\oplus X_b$
另外如果 $a=b$ 請輸出自己

輸出答案。

Input Format

第一行輸入包含兩個數字 $n$ $m$ $(1 \leq n,m \leq 10^ 5)$ 以空格分開

代表 $n$ 個數字,$m$ 筆詢問

第二行包含 $n$ 個正整數,每個數字小於 $100000007$

第三行開始 每行輸入兩個正整數 $a$ $b$ $(1 \leq a \leq b \leq n)$

共有 $m$ 行

Output Format

對於每個詢問,輸出一行正整數,代表答案

Sample Input 1

3 3
6 8 7
1 2
2 2
1 3

Sample Output 1

14
8
9

Hints

xor 在 C/C++ 裡面可以使用 ^ 符號進行運算

xor 其實是在數某個 bit 的 1 到底出現過奇數次還是偶數次

Problem Source

Subtasks

No. Testdata Range Score
1 0~8 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1500 65536 65536 1
5 1500 65536 65536 1
6 1500 65536 65536 1
7 1500 65536 65536 1
8 1500 65536 65536 1