Занулити підвідрізок

Це задача з градерами.

Для масиву додатних цілих чисел $b$ довжини $m$ визначимо $f(b)$ наступним чином:

• нехай початково деяка змінна $x$ рівна $0$;

• за одну монету дозволяється збільшити значення $x$ на $1$;

• за одну монету дозволяється обрати елемент масиву $b_i$ ($1\le i\le m$) та замінити його на $(b_i\oplus x)$, де $\oplus$ позначає операцію побітового виключного АБО;

• $f(b)$ дорівнює мінімальній кількості монет, необхідній для того, щоб зробити всі елементи масиву $b$ одночасно рівними нулю.

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

Задано масив додатних цілих чисел $a$ довжини $n$ та $q$ запитів виду $l$, $r$. Для кожного запиту потрібно знайти $f([a_l,a_{l+1},\dots ,a_r])$.

Вхідні дані

У першому рядку задано три цілі числа $n$, $q$ та $t$ ($1\le n,q\le 2\cdot 10^5$; $1\le t\le 2$) — кількість чисел, кількість запитів та формат запитів відповідно.

У другому рядку задано $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i<2^{60}$) — елементи масиву $a$.

У наступних $q$ рядках задано по два цілі числа $l$ та $r$ ($1\le l\le r\le n$) — параметри $i$-го запиту.

Спочатку буде викликана функція init рівно один раз.

Якщо $t=1$, то буде викликана рівно один раз функція askAll з усіма запитами. Якщо $t=2$, то функція ask буде викликана рівно $q$ разів.

Протокол взаємодії

Вам потрібно реалізувати наступні функції:

void init(integer n, array of integers a)

• $n$ — ціле число, яке позначає довжину масиву;

• $a$ — масив цілих чисел довжиною $n$;

• ця функція нічого не повертає.

integer ask(integer l, integer r)

• $l$ — ціле число, яке позначає ліву межу запиту;

• $r$ — ціле число, яке позначає праву межу запиту;

• ця функція повертає ціле число — $f([a_l,a_{l+1},\dots ,a_r])$.

array of integers askAll(integer q, array of integers l, array of integers r)

• $q$ — ціле число, яке позначає кількість запитів;

• $l$ — масив цілих чисел довжиною $q$; $l_i$ позначає ліву межу $i$-го запиту;

• $r$ — масив цілих чисел довжиною $q$; $r_i$ позначає праву межу $i$-го запиту;

• ця функція повертає масив цілих чисел; $i$-те число має бути рівне відповіді на $i$-й запит.

Вихідні дані

Градер виведе у окремих рядках $q$ цілих чисел — відповіді на запити.

Приклади

Оцінювання

1. ($3$ бали): $t=1$, $a_i=a_1$ для $1\le i\le n$;

2. ($8$ балів): $t=1$, $a_i\ne a_j$ для $i\ne j$;

3. ($3$ бали): $t=1$, $2^m+n\le a_i<2^{m+1}$ для деякого натурального $m$;

4. ($9$ балів): $t=1$, $a_i\le a_{i+1}$ для $1\le i<n$;

5. ($10$ балів): $t=1$, $n,q\le 1000$;

6. ($11$ балів): $t=1$, $l_i=1$ та $r_i=i$ для $1\le i\le q$.

7. ($10$ балів): $t=1$, $n,q\le 50000$;

8. ($25$ балів): $t=1$;

9. ($9$ балів): $t=2$, $n,q\le 10^5$;

10. ($12$ балів): $t=2$.