Масив і XOR

Обмеження на час виконання 4 секунди

Обмеження на використання пам'яті 512 мегабайтів

Задано ціле число $m$ , масив невід'ємних цілих чисел $a$ довжини $n$ та $q$ запитів виду $l_{i}$ , $r_{i}$ . Всі елементи масиву $a$ менші за $2^{m}$ .

Визначимо функцію $f_{i} (x) = min_{j \in [l_{i}, r_{i}]} (a_{j} \oplus x)$ , де $\oplus$ позначає операцію побітового виключного АБО. Для кожного запиту вам потрібно знайти значення $max_{x \in {0, 1, \dots, 2^{m} - 1}} f_{i} (x)$ .

Побітове виключне АБО невід'ємних цілих чисел $a$ та $b$ $(a \oplus b)$ дорівнює невід'ємному цілому числу, у якого у двійковому записі на певній позиції знаходиться одиниця тоді і тільки тоді, коли у двійкових записах $a$ та $b$ на цій позиції знаходяться різні значення. Наприклад, $3_{10} \oplus 5_{10} = 001 1_{2} \oplus 010 1_{2} = 011 0_{2} = 6_{10}$ .

Вхідні дані

У першому рядку задано три цілі числа $n$ , $q$ , $m$ ( $1 \leq n \leq 1 0^{5}$ , $1 \leq q \leq 5 \cdot 1 0^{5}$ , $1 \leq m \leq 50$ ) — довжина масиву, кількість запитів та обмеження на елементи масиву відповідно.

У другому рядку задано $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ ( $0 \leq a_{i} < 2^{m}$ ) — елементи масиву.

У наступних $q$ рядках задано по два цілі числа $l_{i}$ , $r_{i}$ ( $1 \leq l_{i} \leq r_{i} \leq n$ ) — параметри $i$ -го запиту.

Вихідні дані

Для $i$ -го запиту в окремому рядку виведіть одне ціле число — значення $max_{x \in {0, 1, \dots, 2^{m} - 1}} f_{i} (x)$ .

Приклади

Вхідні дані #1

Відповідь #1

Примітка

Розглянемо перший запит.

$f_{1} (0) = min (1 \oplus 0, 3 \oplus 0, 2 \oplus 0, 7 \oplus 0, 1 \oplus 0) = min (1, 3, 2, 7, 1) = 1$

$f_{1} (1) = min (1 \oplus 1, 3 \oplus 1, 2 \oplus 1, 7 \oplus 1, 1 \oplus 1) = min (0, 2, 3, 6, 0) = 0$

$f_{1} (2) = min (1 \oplus 2, 3 \oplus 2, 2 \oplus 2, 7 \oplus 2, 1 \oplus 2) = min (3, 1, 0, 5, 3) = 0$

$f_{1} (3) = min (1 \oplus 3, 3 \oplus 3, 2 \oplus 3, 7 \oplus 3, 1 \oplus 3) = min (2, 0, 1, 4, 2) = 0$

$f_{1} (4) = min (1 \oplus 4, 3 \oplus 4, 2 \oplus 4, 7 \oplus 4, 1 \oplus 4) = min (5, 7, 6, 3, 5) = 3$

$f_{1} (5) = min (1 \oplus 5, 3 \oplus 5, 2 \oplus 5, 7 \oplus 5, 1 \oplus 5) = min (4, 6, 7, 2, 4) = 2$

$f_{1} (6) = min (1 \oplus 6, 3 \oplus 6, 2 \oplus 6, 7 \oplus 6, 1 \oplus 6) = min (7, 5, 4, 1, 7) = 1$

$f_{1} (7) = min (1 \oplus 7, 3 \oplus 7, 2 \oplus 7, 7 \oplus 7, 1 \oplus 7) = min (6, 4, 5, 0, 6) = 0$

Відповідь на цей запит дорівнює $max_{x \in {0, 1, \dots, 2^{3} - 1}} f_{1} (x) = max (1, 0, 0, 0, 3, 2, 1, 0) = 3$ .

Оцінювання

( $4$ бали): $n \leq 100$ , $q \leq 100$ , $m \leq 10$ ;
( $17$ балів): $q = 1$ , $l_{1} = 1$ , $r_{1} = n$ ;
( $16$ балів): $q \leq 2 \cdot 1 0^{5}$ ; $a_{i} \leq a_{i + 1}$ для $1 \leq i < n$ ;
( $17$ балів): $n \leq 1 0^{4}$ , $q \leq 1 0^{4}$ ;
( $26$ балів): $n \leq 5 \cdot 1 0^{4}$ , $m \leq 30$ ;
( $20$ балів): без додаткових обмежень.