Куонг очень разборчив в еде. Чтобы помочь ему избавиться от этой привычки, друзья решили положить на его любимую пиццу различные ингредиенты. Пицца имеет форму круга, где первый и последний куски являются соседними.

Предпочтение Куонга к пицце определяется как максимальная сумма предпочтений последовательных кусков пиццы. Предпочтение отдельного куска пиццы равно сумме предпочтений всех ингредиентов, находящихся на этом куске. Предпочтение куска пиццы без ингредиентов равно 0.

Так как выбор ни одного куска пиццы не имеет смысла, предпочтение пиццы учитывает только случаи выбора одного или более кусков.

Изначально на пицце нет никаких ингредиентов. Друзья Куонга выполняют в общей сложности $Q$ действий одного из двух типов:

• 1 $a$ $b$: положить на кусок $a$ ($1 \le a \le S$) ингредиент с предпочтением $b$ ($-10^9 \le b \le 10^9$).
• 2: спросить, каково текущее предпочтение пиццы Куонга.

Входные данные

В первой строке через пробел заданы количество кусков пиццы $S$ ($1 \le S \le 200\,000$) и количество действий друзей Куонга $Q$ ($1 \le Q \le 500\,000$).

Далее следуют $Q$ строк с описанием действий.

Действие типа 2 встречается как минимум один раз.

Все числа во входных данных являются целыми.

Выходные данные

Для каждого действия типа 2 выведите текущее предпочтение пиццы Куонга.

Примеры

Входные данные 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

Выходные данные 1

6
9
12
9
9