Range Xor Queries

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
hhoangcpascal
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1,A_2,...,A_N\). Nhiệm vụ của bạn là thực hiện \(Q\) truy vấn sau: Tổng \(XOR\) của các giá trị trong phạm vi \([x,y]\) là bao nhiêu?

Input

  • Dòng đầu tiên gồm hai số nguyên dương \(N, Q\) là số lượng giá trị và số truy vấn.
  • Dòng thứ hai gồm \(N\) số nguyên dương \(A_1,A_2,...,A_N (A_i≤10^9)\).
  • \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn, gồm hai số nguyên \(x,y\) \((1≤x≤y≤N)\).

Output

  • In ra \(Q\) dòng, mỗi dòng là kết quả của một truy vấn.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(N,Q≤2.10^3\).
  • Subtask \(2\) (\(50\%\) số điểm): \(N,Q≤2.10^5\).

Example

Test 1

Input 
8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3
Output 
3
0
6
4

Bình luận