Kuong est très difficile avec la nourriture. Pour l'empêcher de faire la fine bouche, ses amis veulent ajouter divers ingrédients sur sa pizza, qu'il adore. Cette pizza est de forme circulaire, où la première part et la dernière part sont adjacentes.

La préférence de la pizza de Kuong est définie comme la valeur maximale de la somme des préférences des parts de pizza consécutives. De plus, la préférence d'une part de pizza est égale à la somme des préférences des ingrédients déposés sur cette part. La préférence d'une part de pizza sans aucun ingrédient est de 0.

Comme il serait étrange de parler de la préférence de la pizza sans choisir aucune part, la préférence de la pizza ne prend en compte que les cas où l'on choisit au moins une part de pizza.

Initialement, aucun ingrédient n'est déposé sur la pizza. Les amis de Kuong effectuent un total de $Q$ opérations, chacune étant l'une des deux suivantes :

• 1 $a$ $b$ : Ajouter un ingrédient ayant une préférence de $b$ ($-10^9 \le b \le 10^9$) sur la part $a$ ($1 \le a \le S$).
• 2 : Demander quelle est la préférence de la pizza actuelle de Kuong.

Entrée

La première ligne contient le nombre de parts de pizza $S$ ($1 \le S \le 200\,000$) et le nombre d'opérations effectuées par les amis de Kuong $Q$ ($1 \le Q \le 500\,000$), séparés par un espace.

Les $Q$ lignes suivantes décrivent les opérations.

L'opération 2 est donnée au moins une fois.

Tous les nombres donnés en entrée sont des entiers.

Sortie

Pour chaque opération 2, affichez la préférence de la pizza de Kuong.

Exemples

Exemples 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

Sortie 1

6
9
12
9
9