Kuong is a very picky eater. To prevent his picky eating, his friends want to put various ingredients on a pizza, which is Kuong's favorite food. This pizza is circular, meaning the first slice and the last slice are adjacent.

The preference of Kuong's pizza is the maximum sum of the preferences of a contiguous sequence of pizza slices. The preference of a pizza slice is equal to the sum of the preferences of the ingredients placed on that slice. The preference of a pizza slice with no ingredients is 0.

Since it is strange to call the preference of a pizza "0" if no slices are selected, the preference of the pizza only considers cases where one or more pizza slices are chosen.

Initially, there are no ingredients on the pizza. Kuong's friends perform one of the following two actions a total of $Q$ times:

• 1 $a$ $b$: Place an ingredient with a preference of $b$ ($-10^9 \le b \le 10^9$) on the $a$-th slice ($1 \le a \le S$).
• 2: Ask what the current preference of the pizza is.

The first line contains the number of pizza slices $S$ ($1 \le S \le 200\,000$) and the number of actions $Q$ ($1 \le Q \le 500\,000$) performed by Kuong's friends, separated by a space.

Following this, $Q$ lines describe the actions.

Action 2 is given at least once.

All numbers given in the input are integers.

For every action 2, output the preference of Kuong's pizza.

Examples

Input 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

Output 1

6
9
12
9
9