시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 512 MB 159 94 57 60.638%

문제

관영이는 쿼리를 좋아하고, XOR도 좋아한다. 그래서 관영이는 XOR을 이용한 쿼리 문제를 좋아한다.

길이가 $N$인 수열 $a_1 , a_2 , \cdots a_N$이 있다. 

이제 관영이는 $Q$개의 쿼리에 답하려 한다. 각 쿼리는 $s_i , e_i$ ($1 \le s_i \le e_i \le N$)의 형태로 들어오고, 그 쿼리의 답은 $a_{s_i}, a_{s_i+1}, \cdots a_{e_i}$을 모두 XOR한 값이다. 

$Q$개의 쿼리가 들어올 때, 각 쿼리의 답을 모두 XOR한 결과를 구하시오. 

입력

첫째 줄에는 $N, Q$가 공백을 사이에 두고 주어진다. ($1 \le N \le 10^6$, $1 \le Q \le 3 \cdot 10^6$)

둘째 줄에는 $a_1, a_2, \cdots a_N$이 공백을 사이에 두고 주어진다. ($0 \le a_i \le 10^9$)

그 후, $Q$개의 줄에 걸쳐서, 각 줄마다 하나의 쿼리 $s_i, e_i$가 공백을 사이에 두고 주어진다. ($1 \le s_i \le e_i \le N$) 

출력

모든 쿼리의 답을 XOR한 값을 출력하시오. 

예제 입력 1

5 3
4 4 4 4 4
1 1
1 2
1 3

예제 출력 1

0

예제 입력 2

5 4
4 4 2 1 0
1 1
1 2
1 3
2 4

예제 출력 2

1

출처

High School > 경기과학고등학교 > 나는 코더다 2018 송년대회 G번