Module: الگوریتم مو

Problem

ایوان یک عدد مورد علاقه k و یک آرایه a_i به طول n دارد. اکنون از شما می خواهد به m درخواست پاسخ دهید.

برای هر پرس و جو داده شده توسط یک جفت اعداد l و r، باید تعداد جفت اعداد صحیح i و j را پیدا کرد به طوری که l ≤ i ≤ j ≤ r و xor از اعداد a_i ، a_i + 1، ...، a_j k است.< br />
ورودی:
خط اول شامل اعداد صحیح n، m و k است (1 ≤ n، m ≤ 10⁵، 0 ≤ k ≤  10 ⁶) — طول آرایه، تعداد درخواست‌ها و شماره مورد علاقه ایوان به ترتیب.
خط دوم شامل n عدد صحیح ai (0 ≤ a_i ≤ 10⁶) — آرایه ایوان.
سپس m خطوط وجود دارد. خط i-ام حاوی اعداد l_i و r_i است (1 ≤ l_i ≤ r< sub>i ≤ n) پرس و جوی i را تعریف می کند.

خروجی:
m خطوط را چاپ کنید، پاسخ سوالات را به ترتیبی که در ورودی نشان داده می شوند.

مثال:
  <بدن>

ورودی	خروجی
6 2 3 1 2 1 1 0 3 16 3 5	7 0
5 3 1 1 1 1 1 1 1 15 24 1 3	9 4 4