쿠옹이는 편식을 많이 한다. 친구들은 쿠옹이의 편식을 막기 위해 쿠옹이가 좋아하는 음식인 피자 위에 다양한 재료를 올리려고 한다. 이 피자는 첫 번째 조각과 마지막 조각이 연속되어 있는 원 모양이다.

쿠옹이의 피자의 선호도는 연속된 피자 조각의 피자 조각의 선호도의 합의 최댓값이다. 또한 피자 조각의 선호도는 그 피자 조각 위에 올라가 있는 재료의 재료의 선호도의 합과 같다. 아무 재료도 올라가 있지 않은 피자 조각의 선호도는 0이다.

아무 피자 조각도 선택하지 않고 피자의 선호도라고 하는 것은 이상하므로 피자의 선호도는 하나 이상의 피자 조각을 고르는 경우만을 포함한다.

최초에 피자 위에는 아무 재료도 올라가 있지 않다. 쿠옹이의 친구들은 총 $Q$번에 걸쳐 다음 두 행동 중 하나를 한다.

• 1 $a$ $b$: $a$($1 \le a \le S$)번 조각 위에 재료의 선호도가 $b$($-10^9 \le b \le 10^9$)인 재료를 올린다.
• 2: 쿠옹이에게 현재 쿠옹이의 피자의 선호도가 몇인지 질문한다.

Input

첫째 줄에 피자의 조각 수 $S(1 \le S \le 200\,000)$와 쿠옹이의 친구들의 행동 수 $Q(1 \le Q \le 500\,000)$가 공백으로 구분되어 주어진다.

이후 $Q$개의 줄에 걸쳐 행동이 주어진다.

행동 2는 적어도 한 번 이상 주어진다.

입력으로 주어지는 모든 수는 정수이다.

Output

행동 2가 주어질 때마다 쿠옹이의 피자의 선호도를 출력하라.

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