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

有多组测试数据。第一行输入一个整数 \(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

对于每次操作 \(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