Traveling in a Color-Constrained Row

You are given n cells arranged in a row. The i-th cell has a color \(c_i\) and a ball with value \(v_i\). You have to process q operations. There are three types of operations:

• Type 1: 1 p x — Change the color of the p-th cell to x, i.e. set \(c_p=x\).
• Type 2: 2 p x — Change the ball value of the p-th cell to x, i.e. set \(v_p=x\).
• Type 3: 3 x k a_1 a_2 \ldots a_k — A travel query. You are given a starting cell \(x\) and a set of colors \(\mathbb{A}=\{a_1,a_2,\ldots,a_k\}\) such that \(c_x\in \mathbb{A}\). Starting from cell \(x\), you can move to an adjacent cell (either \(i-1\) or \(i+1\)) as long as the cell's color is in \(\mathbb{A}\). In each cell you visit, you may choose to remove the ball to gain its value \(v_i\) (each ball can only be removed once). The task is to compute the maximum total value you can collect during this travel. Note that the travel is only imaginary; removals in a query do not affect subsequent queries.

In other words, for a query of type 3, you need to calculate the sum of \(v_i\) over all cells in the connected component (i.e. contiguous segment) containing \(x\) where the cell's color \(c_i\) is in \(\mathbb{A}\>.

inputFormat

The first line contains two integers n and q — the number of cells and the number of operations, respectively.

The second line contains n integers \(c_1, c_2, \ldots, c_n\) representing the initial colors of the cells.

The third line contains n integers \(v_1, v_2, \ldots, v_n\) representing the initial ball values in the cells.

Each of the following q lines represents an operation in one of the following formats:

• 1 p x — change \(c_p\) to x.
• 2 p x — change \(v_p\) to x.
• 3 x k a_1 a_2 ... a_k — a travel query with starting cell \(x\) and allowed color set \(\{a_1, a_2, \ldots, a_k\}\). It is guaranteed that \(c_x \in \{a_1,a_2,\ldots,a_k\}\).

outputFormat

For each operation of type 3, output one line containing a single integer — the maximum total value you can gain in that travel.

sample

5 5
1 2 3 1 2
1 2 3 4 5
3 3 2 3 1
1 2 3
3 3 2 3 1
2 4 10
3 5 2 2 1

7
10
15