Hay $n$ celdas dispuestas en una fila. La celda $i$ tiene un color $c_i$ y contiene una bola de valor $v_i$.
Vas a realizar varios viajes por las celdas. Para cada viaje recibirás un entero $x$ y un conjunto de colores $A = \{a_1, a_2, \cdots, a_k\}$, con $c_x \in A$. El viaje empieza en la celda $x$. Durante el viaje, si estás en la celda $i$, puedes moverte a continuación a la celda $(i - 1)$ o $(i + 1)$. Ten en cuenta que no puedes salir de estas $n$ celdas. Además, en todo momento el color de la celda en la que estás debe pertenecer al conjunto $A$.
Cuando estés en la celda $i$, puedes elegir retirar la bola de esa celda y obtener su valor $v_i$. Como solo hay una bola en cada celda, solo puedes retirar la bola de cada celda una vez.
Tu tarea es procesar $q$ operaciones en orden. Cada operación es de uno de los tres tipos siguientes:
- $1\ p\ x$: Cambia $c_p$ a $x$.
- $2\ p\ x$: Cambia $v_p$ a $x$.
- $3\ x\ k\ a_1\ a_2\ \ldots\ a_k$: Dados la celda inicial $x$ y el conjunto de colores $A = \{a_1, a_2, \cdots, a_k\}$ de un viaje, imagina que lo realizas y calcula el máximo valor total que puedes obtener. Ten en cuenta que este viaje es solo imaginario, por lo que las bolas no se retirarán realmente. Es decir, todas las consultas son independientes.
Entrada
Hay varios casos de prueba. La primera línea de la entrada contiene un entero $T$ que indica el número de casos de prueba. Para cada caso:
La primera línea contiene dos enteros $n$ y $q$ ($1 \le n \le 10^5, 1 \le q \le 10^5$), que indican el número de celdas y el número de operaciones.
La segunda línea contiene $n$ enteros $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le n$), donde $c_i$ es el color inicial de la celda $i$.
La tercera línea contiene $n$ enteros $v_1, v_2, \ldots, v_n$ ($1 \le v_i \le 10^9$), donde $v_i$ es el valor inicial de la bola de la celda $i$.
De las siguientes $q$ líneas, la línea $i$ describe la operación $i$. El formato de entrada es el siguiente:
- $1\ p\ x$: $1 \le p \le n$ y $1 \le x \le n$.
- $2\ p\ x$: $1 \le p \le n$ y $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$ y $c_x \in \{a_1,a_2,\cdots,a_k\}$.
Se garantiza que ni la suma de $n$ ni la suma de $q$ de todos los casos de prueba superan $3 \times 10^5$. Además, la suma de $k$ de todos los casos de prueba no supera $10^6$.
Salida
Para cada operación de tipo 3, imprime una línea con un entero que indique el máximo valor total que puedes obtener.
Ejemplos
Entrada 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
Salida 1
100 110 1200 21211 100010 4000000