Kuong jest bardzo wybredny, jeśli chodzi o jedzenie. Aby temu zaradzić, jego przyjaciele postanowili umieścić różne składniki na pizzy, którą Kuong lubi. Pizza ma kształt koła, w którym pierwszy i ostatni kawałek są ze sobą sąsiadujące.

Preferencja pizzy Kuonga to maksymalna suma preferencji dla ciągu sąsiadujących kawałków pizzy. Preferencja pojedynczego kawałka pizzy jest równa sumie preferencji składników umieszczonych na tym kawałku. Preferencja kawałka pizzy, na którym nie ma żadnych składników, wynosi 0.

Ponieważ wybór żadnego kawałka pizzy nie ma sensu w kontekście preferencji, przyjmuje się, że preferencja pizzy dotyczy tylko przypadków, w których wybrano co najmniej jeden kawałek.

Początkowo na pizzy nie ma żadnych składników. Przyjaciele Kuonga wykonują łącznie $Q$ operacji, z których każda jest jednym z dwóch poniższych typów:

• 1 $a$ $b$: Na kawałku $a$ ($1 \le a \le S$) umieszczany jest składnik o preferencji $b$ ($-10^9 \le b \le 10^9$).
• 2: Pytanie o aktualną preferencję pizzy Kuonga.

W pierwszej linii podano liczbę kawałków pizzy $S(1 \le S \le 200\,000)$ oraz liczbę operacji $Q(1 \le Q \le 500\,000)$, oddzielone spacją.

Następnie podano $Q$ linii opisujących operacje.

Operacja typu 2 występuje co najmniej raz.

Wszystkie liczby podane na wejściu są liczbami całkowitymi.

Dla każdej operacji typu 2 wypisz aktualną preferencję pizzy Kuonga.

Przykład

Wejście 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

Wyjście 1

6
9
12
9
9