Kuong es muy selectivo con la comida. Para evitar que Kuong sea tan selectivo, sus amigos quieren poner varios ingredientes sobre una pizza, la cual es su comida favorita. Esta pizza tiene forma circular, donde la primera y la última porción son adyacentes.

La preferencia de la pizza de Kuong es el valor máximo de la suma de las preferencias de una secuencia de porciones de pizza contiguas. Además, la preferencia de una porción de pizza es igual a la suma de las preferencias de los ingredientes colocados sobre dicha porción. La preferencia de una porción de pizza sin ingredientes es 0.

Dado que no tiene sentido hablar de la preferencia de la pizza sin elegir ninguna porción, la preferencia de la pizza solo considera los casos en los que se elige una o más porciones de pizza.

Inicialmente, no hay ingredientes sobre la pizza. Los amigos de Kuong realizan un total de $Q$ acciones, cada una de las cuales es una de las siguientes:

• 1 $a$ $b$: Colocar un ingrediente con una preferencia de ingrediente de $b$ ($-10^9 \le b \le 10^9$) sobre la porción $a$ ($1 \le a \le S$).
• 2: Preguntar cuál es la preferencia de la pizza actual de Kuong.

Entrada

La primera línea contiene el número de porciones de pizza $S$ ($1 \le S \le 200\,000$) y el número de acciones de los amigos de Kuong $Q$ ($1 \le Q \le 500\,000$), separados por un espacio.

Luego, se proporcionan las acciones a lo largo de $Q$ líneas.

La acción 2 se proporciona al menos una vez.

Todos los números proporcionados en la entrada son enteros.

Salida

Por cada acción 2 proporcionada, imprime la preferencia de la pizza de Kuong.

Ejemplos

Entrada 1

5 12
1 1 3
1 2 3
1 3 -5
2
1 5 3
2
1 4 3
2
1 4 -5
2
1 3 4
2

Salida 1

6
9
12
9
9