問題文

長さ$N$の整数列$A$が与えられます。クエリが$Q$個与えられるので、順に処理してください。

クエリは以下の2種類です。

• 1 i v: $A_i$を$v$で置き換える。
• 2 l r: $[A_l,\ A_{l+1},\ldots,\ A_r]$の連続部分列で論理和(ビット単位OR)が$2^K-1$と等しいものがあるかを判定し、ある場合は条件を満たす連続部分列のうち最短のものの長さを出力する。

※解説ページの方にヒントを３つ置いてますので、考察に詰まった際は参考にしてください。

入力

$N \enspace K$
$A_1 \enspace A_2\ \ldots\ A_N$
$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 16$
• $1 \leq Q \leq 10^4$
• 全ての$v \in A$は、$0 \leq v < 2^K$を満たす
• 全てのクエリ1は、$1 \leq i \leq N$、$0 \leq v < 2^K$を満たす
• 全てのクエリ2は、$1 \leq l \leq r \leq N$を満たす
• 入力は全て整数である

出力

クエリ2に対して、もし条件を満たす連続部分列がある場合は最短のものの長さを、ない場合は-1を各行に出力してください。

サンプル

3 2
1 2 3
4
2 1 2
2 1 3
1 2 1
2 1 2

2
1
-1

6 4
14 12 15 12 13 11
10
2 1 2
1 3 4
1 2 6
1 5 5
2 4 6
1 5 15
1 3 3
2 1 5
1 3 11
2 2 4

-1
2
1
2