XOR#8277
У Назара є улюблене число і масив a_i довжини . Він просить вас відповісти на запитів.
Для кожного запиту, заданого парою чисел і , потрібно визначити кількість пар цілих чисел і таких, що l \le i \le j \le r і xor (позначається знаком ^ у C++) чисел a_i, a_{i+1}, \ldots, a_j дорівнює .
У першому рядку дано цілі числа , і (1 \le n, m \le 10^5; 0 \le k \le 10^6) — довжина масиву, кількість запитів і улюблене число Назара відповідно.
У другому рядку записано цілих чисел a_i (0 \le a_i \le 10^6) — наявний у Назара масив. Далі йдуть рядків. У -му рядку записані числа l_i і r_i (1 \le l_i, r_i \le n), що визначають -й запит.
Виведіть рядків, кожен з яких містить відповідь на відповідний запит.
Приклад 1
Приклад 2