XOR

У Назара є улюблене число k і масив a[i] довжини n. Він просить вас відповісти на m запитів.

Для кожного запиту, заданого парою чисел l і r, потрібно визначити кількість пар цілих чисел i і j таких, що l ≤ i ≤ j ≤ r і xor (позначається знаком ^ у C++) чисел a[i], a[i+1], …, a[j] дорівнює k.

Вхідні дані

У першому рядку дано цілі числа n, m і k (1 ≤ n, m ≤ 10^5; 0 ≤ k ≤ 10^6) — довжина масиву, кількість запитів і улюблене число Назара відповідно.

У другому рядку записано n цілих чисел a[i] (0 ≤ a[i] ≤ 10^6) — наявний у Назара масив. Далі йдуть m рядків. У i-му рядку записані числа l[i] і r[i] (1 ≤ l[i], r[i] ≤ n), що визначають i-й запит.

Вихідні дані

Виведіть m рядків, кожен з яких містить відповідь на відповідний запит.

Приклади