XOR

Nazarın sevimli k ədədi və uzunluğu n olan a[i] massiv var. İndi o, sizdən m sorğuya cavab verməyinizi xahiş edir.

Hər bir sorğu üçün, l və r ədədləri ilə verilən cütlükdə, l ≤ i ≤ j ≤ r və xor (C++ dilində ^ işarəsi ilə göstərilir) a[i]; a[i+1]; …; a[j] ədədlərinin k-yə bərabər olduğu tam ədədlər i və j cütlərinin sayını tapmaq tələb olunur.

Giriş məlumatları

Birinci sətirdə tam ədədlər n; m və k (1 ≤ n, m ≤ 10^5; 0 ≤ k ≤ 10^6) — massiv uzunluğu, sorğuların sayı və Nazarın sevimli ədədi verilmişdir.

İkinci sətirdə n tam ədəd a[i] (0 ≤ **a[i] ≤ 10^6) — Nazarın malik olduğu massiv verilmişdir. Sonra m sətir gəlir. i-ci sətirdə l[i] və r[i] (1 ≤ l[i], r[i] ≤ n) ədədləri, i-ci sorğunu müəyyən edir.

Çıxış məlumatları

m sətir çıxarın, sorğulara cavablar.