Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P193SUMF - Vẫn là truy vấn trên mảng

Time limit: 0.2s

Cho một mảng a gồm n phần tử, một số nguyên không âm k và m truy vấn.

Mỗi truy vấn gồm 2 giá trị li và ri, yêu cầu tìm ra số mảng con nằm trong đoạn [l, r] mà tổng xor của mảng con (tức phép xor dồn mọi phần tử trong mảng) đúng bằng k.

Input

Dòng đầu tiên chứa ba số nguyên n, m, k (1 ≤ n, m ≤ 105, 0 ≤ k ≤ 106) – lần lượt là kích thước mảng, số truy vấn và hằng số k được sử dụng trong truy vấn.

Dòng thứ hai chứa n số nguyên ai (0 ≤ ai ≤ 106) thể hiện mảng a.

m dòng tiếp theo, dòng thứ i gồm hai số nguyên li, ri (1 ≤ l ≤ r ≤ n) mô tả truy vấn thứ i.

Output

In ra m dòng, dòng thứ i là câu trả lời cho truy vấn thứ i.

Example

Input

Output

5 3 1

1 1 1 1 1

1 5

2 4

1 3

9

4

4

"Wake up."


Được gửi lên bởi:Admin
Ngày:2019-07-27
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.