Побітова імплікація

Limits: 3 sec., 256 MiB

У Зеника є набір із $n$ чисел, кожне з яких є $k$-бітовим. Іншими словами, кожне з чисел в межах $[0, 2^k)$.

Зеника цікавить операція побітової імплікації $x \to y = (2^k - 1 - x)$ $OR$ $y$, де $OR$ – операція побітового АБО. Зеник виконує наступну дію поки не залишиться одне число: взяти 2 числа $x$, $y$ з поточного набору, видалити їх та додати $x \to y$.

Марічці цікаво, яку мінімальну кількість одиничних бітів може мати число, яке залишилось в результаті операцій Зеника.

Але все не так просто, Марічка вирішила задавати Зенику два типи запитів:

1. Змінити значення $a_{pos}$ на $val$.

2. Порахувати, яку мінімальну кількість одиничних бітів може мати фінальне число, якщо в початковому наборі всі числа $a_l, a_{l+1}, \dots, a_r$.

Допоможіть Зенику розв’язати таку задачу.

Input

У першому рядку задано 3 цілих числа $n$, $k$, $q$ — кількість чисел, кількість бітів в кожному числі та кількість запитів Марічки.

У наступному рядку задано $n$ цілих чисел $a_i$.

У наступних $q$ рядках задано запити у наступному форматі:

$1\ pos\ val$ – запит першого типу означає, що потрібно змінити значення $a_{pos}$ на $val$.

$2\ l\ r$ – запит другого типу означає, що потрібно порахувати відповідь для початкового набору $a_l, a_{l+1}, \dots, a_r$.

Output

Для кожного запиту другого типу виведіть мінімальну кількість одиничних бітів.

Constraints

$1 \le n, q \le 2 \cdot 10^5$,

$1 \le k \le 30$,

$0 \le a_i, val < 2^k$,

$1 \le pos \le n$, $1 \le l \le r \le n$.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 3 7 4 3 2 1 2 2 2 2 1 4 1 4 6 1 3 7 2 3 4 1 1 0 2 1 4	2 1 2 0

Notes

Розглянемо операції з прикладу:

1. Порахувати відповідь для лише другого значення [3], у ньому 2 одиничні біти.

2. Порахувати відповідь для усіх значень, одне з можливих останніх значень є 2, у якому 1 одиничний біт.

3. Змінити четверте значення на 6, тепер масив рівний [4, 3, 2, 6].

4. Змінити третє значення на 7, тепер масив рівний [4, 3, 7, 6].

5. Порахувати відповідь для значень [7, 6]. Можна отримати значення 6, у якому 2 одиничних біти.

6. Змінити перше значення на 0, тепер масив рівний [0, 3, 7, 6].

7. Порахувати відповідь для всіх значень, цього разу можливо отримати фінальне значення 0.