Description

有 $n$ 个格子排成一行，第 $i$ 个格子的颜色为 $c_i$，上面放置着一个权值为 $v_i$ 的球。

您将要在格子中进行若干次旅行。每次旅行时，您会得到旅行的起点 $x$ 与一个颜色集合 $\mathbb{A} = \{a_1, a_2, \cdots, a_k\}$，且保证 $c_x \in \mathbb{A}$。旅行将从第 $x$ 个格子上开始。在旅行期间，如果您在格子 $i$ 处，那么您可以向格子 $(i - 1)$ 或 $(i + 1)$ 处移动，但不能移动到这 $n$ 个格子之外。且在任意时刻，您所处的格子的颜色必须在集合 $\mathbb{A}$ 中。

当您位于格子 $i$ 时，您可以选择将格子上的球取走，并获得 $v_i$ 的权值。由于每个格子上只有一个球，因此一个格子上的球只能被取走一次。

您的任务是依次处理 $q$ 次操作，每次操作形如以下三种操作之一：

• $1\; p \; x$：将 $c_p$ 修改为 $x$。
• $2\; p \; x$：将 $v_p$ 修改为 $x$。
• $3\; x\; k\; a_1\; a_2 \; \ldots\; a_k$：给定旅行的起点 $x$ 与一个颜色集合 $\mathbb{A} = \{a_1, a_2, \cdots, a_k\}$。假设如果进行这样的一次旅行，求出取走的球的权值之和最大是多少。注意，由于我们仅仅假设进行一次旅行，因此并不会真的取走任何球。即，所有询问之间是独立的。

Input Format

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入两个整数 $n$ 和 $q$（$1 \leq n \leq 10^5$，$1 \leq q \leq 10^5$）表示格子的数量和操作的数量。

第二行输入 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \leq c_i \leq n$），其中 $c_i$ 表示第 $i$ 个格子的初始颜色。

第三行输入 $n$ 个整数 $v_1, v_2, \ldots, v_n$（$1 \leq v_i \leq 10^9$），其中 $v_i$ 表示第 $i$ 个格子里的球的初始权值。

对于接下来 $q$ 行，第 $i$ 行描述第 $i$ 次操作，格式如下：

• $1\; p\; x$：保证 $1 \leq p \leq n$ 且 $1 \leq x \leq n$。
• $2\; p\; x$：保证 $1 \leq p \leq n$ 且 $1 \leq x \leq 10^9$。
• $3\; x\; k\; a_1\; a_2\; \ldots \; a_k$：保证 $1 \leq x \leq n$ 且 $1 \leq a_1 < a_2 < \ldots < a_k \leq n$ 且 $c_x \in \{a_1, a_2, \cdots, a_k\}$。

保证所有数据 $n$ 之和与 $q$ 之和均不超过 $3 \times 10^5$，且所有数据 $k$ 之和不超过 $10^6$。

Output Format

对于每次操作 $3$ 输出一行一个整数，表示取走的球的权值之和的最大值。

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

100
110
1200
21211
100010
4000000