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

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.