Module: Algoritma Mo

Problem

Evan mempunyai nombor k kegemaran dan tatasusunan a_i panjang n. Kini ia meminta anda menjawab m permintaan.

Bagi setiap pertanyaan yang diberikan oleh sepasang nombor l dan r, ia dikehendaki mencari bilangan pasangan integer i dan j supaya l ≤ i ≤ j ≤ r dan xor daripada nombor a_i , a_i + 1, ..., a_j ialah k.< br />
Input:
Baris pertama mengandungi integer n, m dan k (1 ≤ n, m ≤ 10⁵, 0 ≤ k ≤  10 ⁶) — panjang tatasusunan, bilangan permintaan dan nombor kegemaran Evan, masing-masing.
Baris kedua mengandungi n integer ai (0 ≤ a_i ≤ 10⁶) — Tatasusunan Evan.
Kemudian terdapat m baris. Baris ke-i mengandungi nombor l_i dan r_i (1 ≤ l_i ≤ r< sub>i ≤ n) mentakrifkan pertanyaan ke-i.

Output:
Cetak m baris, jawapan kepada soalan mengikut susunan yang muncul dalam input.

Contoh:
 

Input	Output
6 2 3 1 2 1 1 0 3 16 3 5	7 0
5 3 1 1 1 1 1 1 15 24 1 3	9 4 4