Tu tarea consiste en mantener una lista de arreglos que inicialmente contiene un solo arreglo. Debes procesar los siguientes tipos de consultas:

1. Establecer el valor a del arreglo ~k~ en ~x~.
2. Calcular la suma de los valores en el rango ~[a,b]~ del arreglo ~k~.
3. Crear una copia del arreglo ~k~ y añadirla al final de la lista.

Entrada

• La primera línea de entrada contiene dos enteros ~n~ y ~q~: el tamaño del arreglo y el número de consultas.
• La siguiente línea contiene ~n~ enteros ~t_1, t_2, \ldots, t_n~: el contenido inicial del arreglo.
• Finalmente, hay ~q~ líneas que describen las consultas. El formato de cada línea es uno de los siguientes: "~1~ ~k~ ~a~ ~x~", "~2~ ~k~ ~a~ ~b~" ó "~3~ ~k~".

Salida

Imprime la respuesta a cada consulta de suma.

Restricciones

• ~1 \leq n, q \leq 2 \cdot 10^5~
• ~1 \leq t_i, x \leq 10^9~
• ~1 \leq a \leq b \leq n~

Ejemplo de Entrada

5 6
2 3 1 2 5
3 1
2 1 1 5
2 2 1 5
1 2 2 5
2 1 1 5
2 2 1 5

Ejemplo de Salida

13
13
13
15