题目描述

There are $n$ cells arranged in a row. The $i$-th cell has a color $c_i$ and contains a ball with value $v_i$.

You're going to travel several times in the cells. For each travel, you'll be given an integer $x$ and a set of colors $\mathbb{A} = \{a_1, a_2, \cdots, a_k\}$ where $c_x \in \mathbb{A}$. The travel starts from cell $x$. During the travel, if you're located in cell $i$ you can next move to cell $(i - 1)$ or $(i + 1)$. Note that you can't move out of these $n$ cells. Also at any time, the color of cell you're located in must belong to set $\mathbb{A}$.

When you're in cell $i$, you can choose to remove the ball in the cell and gain its value $v_i$. As there is only one ball in each cell, you can only remove the ball from each cell once.

Your task is to process $q$ operations in order. Each operation is one of the following three types:

• $1\; p \; x$: Change $c_p$ to $x$.
• $2\; p \; x$: Change $v_p$ to $x$.
• $3\; x\; k\; a_1\; a_2 \; \ldots\; a_k$: Given the starting cell $x$ and the color set $\mathbb{A} = \{a_1, a_2, \cdots, a_k\}$ of a travel, imagine that you're going on this travel, calculate the maximum total value you can gain. Note that this travel is only an imagination, thus the balls won't be truely removed. That is, all queries are independent.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $q$ ($1 \leq n \leq 10^5$, $1 \leq q \leq 10^5$) indicating the number of cells and the number of operations.

The second line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq n$) where $c_i$ is the initial color of the $i$-th cell.

The third line contains $n$ integers $v_1, v_2, \ldots, v_n$ ($1 \leq v_i \leq 10^9$) where $v_i$ is the initial value of ball in the $i$-th cell.

For the following $q$ lines, the $i$-th line describes the $i$-th operation. The input format is listed as follows:

• $1\; p\; x$: $1 \leq p \leq n$ and $1 \leq x \leq n$.
• $2\; p\; x$: $1 \leq p \leq n$ and $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$ and $c_x \in \{a_1, a_2, \cdots, a_k\}$.

It's guaranteed that neither the sum of $n$ nor the sum of $q$ of all test cases will exceed $3 \times 10^5$. Also the sum of $k$ of all test cases will not exceed $10^6$.

输出格式

For each operation of type $3$ output one line containing one integer, indicating the maximum total value you can gain.

题目大意

【题目描述】

有 $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\}$。假设如果进行这样的一次旅行，求出取走的球的权值之和最大是多少。注意，由于我们仅仅假设进行一次旅行，因此并不会真的取走任何球。即，所有询问之间是独立的。

【输入格式】

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

【输出格式】

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