$n$ 個のマスが一列に並んでいます。$i$ 番目のマスの色は $c_i$ で、値 $v_i$ のボールが入っています。
あなたはこれらのマスを何度か旅します。各旅について、整数 $x$ と色の集合 $A = \{a_1, a_2, \cdots, a_k\}$ が与えられ、$c_x \in A$ を満たします。旅はマス $x$ から始まります。旅の途中でマス $i$ にいる場合、次にマス $(i - 1)$ または $(i + 1)$ に移動できます。この $n$ 個のマスの外に出ることはできません。また、どの時点でも、現在いるマスの色は集合 $A$ に属していなければなりません。
マス $i$ にいるとき、そのマスのボールを取り除いて値 $v_i$ を得ることを選べます。各マスにはボールが $1$ つしかないため、各マスからボールを取り除けるのは $1$ 回だけです。
あなたの課題は $q$ 回の操作を順に処理することです。各操作は次の $3$ 種類のいずれかです:
- $1\ p\ x$: $c_p$ を $x$ に変更します。
- $2\ p\ x$: $v_p$ を $x$ に変更します。
- $3\ x\ k\ a_1\ a_2\ \ldots\ a_k$: 旅の開始マス $x$ と色の集合 $A = \{a_1, a_2, \cdots, a_k\}$ が与えられます。この旅をすると仮定して、得られる値の総和の最大値を計算してください。この旅は仮定にすぎないため、ボールが実際に取り除かれることはありません。つまり、すべてのクエリは独立です。
入力
複数のテストケースがあります。入力の最初の行には、テストケースの個数を表す整数 $T$ が与えられます。各テストケースについて:
最初の行には、マスの数と操作の数を表す $2$ 個の整数 $n$ と $q$ が与えられます($1 \le n \le 10^5, 1 \le q \le 10^5$)。
次の行には $n$ 個の整数 $c_1, c_2, \ldots, c_n$ が与えられます($1 \le c_i \le n$)。$c_i$ は $i$ 番目のマスの初期の色です。
$3$ 行目には $n$ 個の整数 $v_1, v_2, \ldots, v_n$ が与えられます($1 \le v_i \le 10^9$)。$v_i$ は $i$ 番目のマスのボールの初期の値です。
続く $q$ 行のうち $i$ 行目は $i$ 番目の操作を表します。入力形式は次のとおりです:
- $1\ p\ x$: $1 \le p \le n$ かつ $1 \le x \le n$。
- $2\ p\ x$: $1 \le p \le n$ かつ $1 \le x \le 10^9$。
- $3\ x\ k\ a_1\ a_2\ \ldots\ a_k$: $1 \le x \le n$、$1 \le a_1 < a_2 < \ldots < a_k \le n$ かつ $c_x \in \{a_1,a_2,\cdots,a_k\}$。
すべてのテストケースにわたる $n$ の総和と $q$ の総和は、いずれも $3 \times 10^5$ 以下であることが保証されます。また、すべてのテストケースにわたる $k$ の総和は $10^6$ 以下です。
出力
種類 3 の各操作について、得られる値の総和の最大値を表す整数を $1$ 行に出力してください。
入出力例
入力 1
2 5 10 1 2 3 1 2 1 10 100 1000 10000 3 3 1 3 3 3 2 2 3 2 5 20000 2 3 200 3 3 2 1 3 3 3 3 1 2 3 1 3 4 2 1 100000 1 2 2 3 1 2 1 2 4 1 1 2 3 4 1000000 1000000 1000000 1000000 3 4 4 1 2 3 4
出力 1
100 110 1200 21211 100010 4000000