I hate Associative Property

だれさんは結合法則が嫌いです。ある日、だれさんは次のような関数 を見つけました。

この関数は一般に となるので、結合法則を満たしません。 だれさんはこの関数を非常に気に入ったため、この関数を使って以下のような問題を考えました。解いてください。

長さ の整数列 が与えられます。 個のクエリが与えられるので処理してください。

• と変更する。

• を出力する。

ただし で を満たす唯一の整数 を表します。

入力は以下の形式で与えられる。

各クエリは以下のいずれかの形式で与えられる。

• type0のクエリにおいて、
• type1のクエリにおいて、 （特に であることに注意せよ。）

4 3
4 8 4 4
1 2 3
0 1 8
1 1 4

6
5

クエリ では 、クエリ では となります。

10 10
133403202 48156701 430605633 221185434 63259974 744846636 519917398 555439784 822174706 352853132
1 5 6
1 2 7
0 1 480330587
0 1 618069247
1 3 6
0 10 77287957
1 1 4
1 3 8
0 8 536865211
1 3 8

404053305
170911907
594492739
551083457
306761338
796596228