数式が表示されない不具合が発生している場合は次の対応をお願いします．

https://twitter.com/yukicoder/status/1191757446596812800?s=20

注意

この問題は問題「紲星」の変更クエリがある，オンライン版です．制約も少し違います．

この問題では正しい解法だとしても，Python などの低速な言語では TLE になる可能性があります (ごめんなさい)

問題文

長さ $N$ の整数列 $A$ が与えられます．はじめ，数列 $A$ の $i$ 番目の値は $A_i$ です．
以下の二種類のクエリが合計 $Q$ 個与えられるので，オンラインで処理してください．

• $1\ X\ Y$

  • クエリ $1$： 要素 $A_X$ の値を $Y$ に変更してください．

• $2\ L\ R$

  • クエリ $2$： 以下の関数 $f$ の最小値を求めてください．
  • $\displaystyle f(x) = \sum_{k = L}^{R} |x - A_k|$

入力はエンコードされて与えられます．詳細は「デコード方法」を参照してください．

入力

$N\ Q$
$A_1\ A_2\ \cdots\ A_{N - 1}\ A_N$
${\rm query}_1$
$\vdots$
${\rm query}_Q$

• $1 \le N, Q < \color{red}{2^{16}}$
• $\color{red} {0} \le A_i < \color{red}{2^{40}}$
• クエリ $2$ が少なくとも一つ含まれる．
• $i$ 番目のクエリ ${\rm query}_i$ は以下のいずれかの形式と制約で与えられます．

• $1\ X\ Y$

  • $1 \le X \le N$
  • $\color{red} {0} \le Y < \color{red}{ 2^{40}}$
  • $X$ と $Y$ はエンコードされて与えられる．

• $2\ L\ R$

  • $1 \le L,R \le N$
  • $L$ と $R$ はエンコードされて与えられる．
• 入力はすべて整数．

制約はエンコード前の値に対するものです．エンコード後の値が上記の制約を満たすとは限らないことに注意してください．

デコード方法

エンコードされた値は，デコードしてクエリに答えてください．デコードは以下のように行います．

あるクエリについて，そのクエリ以前のクエリ $2$ に対する答えをすべて bitwise-xor したものを $s$ とおく (クエリ $2$ がまだ与えられていないとき $s = 0$ とする)．

そのクエリについて，
$L, R, X$ は $s \bmod 2^{16}$ と bitwise-xor したものにそれぞれ置き換える．
$Y$ は $s \bmod 2^{40}$ と bitwise-xor したものに置き換える．
$L > R$ であるとき，この $2$ つを入れ替える．

ここで，$\bmod$ とは整数剰余であり，bitwise-xor とは $2$ 進表記した際の各桁を xor する演算である．

出力

各クエリ $2$ に対し，答えを整数で一行に出力してください．

クエリ $2$ に対する答えは必ず非負整数になることが証明できます．

サンプル

5 5
1 2 3 4 5
2 1 5
2 4 2
1 7 1
2 7 1
2 7 1

6
2
1
3

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

5 3
1 3 3 3 3
2 1 3
1 3 3
2 3 3

2
0

5 3
1 3 3 3 3
2 1 3
1 1 1
2 1 1

12 12
297387055196 77695545773 487710247651 968023697408 232897057651 196525168957 345567455566 471000070300 447869301680 760529722399 1046863926892 756936270335
1 11 517903130960
2 7 2
1 64976 1015085258696
2 64983 64981
1 9451 82208228357
1 9448 746558666809
2 9441 9450
1 45940 543898836941
2 45945 45949
2 22880 22889
2 51967 51959
1 54322 410448003839

1294183628244
410014701878
1012725946269
1042494843413
1557941228433
2349585145539

12 12
297387055196 77695545773 487710247651 968023697408 232897057651 196525168957 345567455566 471000070300 447869301680 760529722399 1046863926892 756936270335
1 11 517903130960
2 2 7
1 4 829005310492
2 1 3
1 9 416718987495
1 10 961934269659
2 3 8
1 11 993417964722
2 2 6
2 3 10
2 4 12
1 10 538835769031