Bitwise implication

Limits: 3 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk has a set of \(n\) numbers, each of which is \(k\)-bit. In other words, each of the numbers is within the range \([0, 2^k)\).

Zenyk is interested in the bitwise implication operation \(x \to y = (2^k - 1 - x)\) \(OR\) \(y\), where \(OR\) is the bitwise OR operation. Zenyk performs the following action until only one number is left: take 2 numbers \(x\), \(y\) from the current set, remove them, and add \(x \to y\).

Marichka is wondering what is the minimum number of set bits the remaining number can have as a result of Zenyk’s operations.

However, it’s not that simple, Marichka decided to ask Zenyk two types of queries:

1. Change the value of \(a_{pos}\) to \(val\).

2. Calculate the minimum number of set bits the final number can have if the initial set consists of all numbers \(a_l, a_{l+1}, \dots, a_r\).

Help Zenyk solve this problem.

Input

The first line contains 3 integers \(n\), \(k\), \(q\) — the number of numbers, the number of bits in each number, and the number of Marichka’s queries.

The next line contains \(n\) integers \(a_i\).

The next \(q\) lines contain queries in the following format:

\(1\ pos\ val\) – a query of the first type means that you need to change the value of \(a_{pos}\) to \(val\).

\(2\ l\ r\) – a query of the second type means that you need to calculate the answer for the initial set \(a_l, a_{l+1}, \dots, a_r\).

Output

For each query of the second type, output the minimum number of set bits.

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

Let’s consider the operations from the example:

1. Calculate the answer for only the second value [3], it has 2 set bits.

2. Calculate the answer for all values, one of the possible final values is 2, which has 1 set bit.

3. Change the fourth value to 6, now the array is equal to [4, 3, 2, 6].

4. Change the third value to 7, now the array is equal to [4, 3, 7, 6].

5. Calculate the answer for the values [7, 6]. We can obtain the value 6, which has 2 set bits.

6. Change the first value to 0, now the array is equal to [0, 3, 7, 6].

7. Calculate the answer for all values, this time it is possible to obtain the final value 0.