한창 프로그래밍 공부를 하는 피에로는 N개의 수가 있을 때( 1 <= N <= 200,000 ), 연속된 구간의 최대 합을 구하고 있다. 하지만 피에로의 친구 어릿광대는 같이 놀지 않고 공부를 하는 피에로가 야속해서 옆에서 Q( 1 <= Q <= 200,000 )개의 제안을 한다.

질문의 종류는 2가지가 있는데, 다음과 같다.

• 0 a b : a번째 위치의 값을 b로 바꾼다.
• 1 : 연속된 숫자들의 최대 합을 답한다.

피에로를 도와 어릿광대에게 대신 답해주자. < 반드시 하나 이상을 골라야 한다. >

입력

• 처음 줄에는 N 과 Q가 입력된다.
• 다음 줄에는 -1000 이상 1000 이하의 N개의 데이터가 입력되며,
• 그 다음줄부터 Q개에 걸쳐 제안이 들어온다.

출력

입출력 예

5 5
8 -3 5 -7 6
1
0 4 -2
1
0 3 -3
1


출력

10
14
8

입출력 보충

• [8 -3 5] -7 6 구간의 합이 최대이므로 이 합인 10을 출력한다.
• 8 -3 5 [-2] 6 으로 -7 을 -2로 갱신한다.
• [8 -3 5 -2 6] 구간의 합이 최대이므로 이 합인 14를 출력한다.
• 8 -3 [-3] -2 6 으로 5 를 -3으로 갱신한다.
• [8] -3 -3 -2 6 구간의 합이 최대이므로 이 합인 8을 출력한다.

출처:pl0892029