Statement is not available in English language
C. 피자 (U+1F355 U+1F60B U+1F92E)
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

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

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

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

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

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

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

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

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

Output

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

Example
Input
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
6
9
12
9
9