쿠옹이는 편식을 많이 한다. 친구들은 쿠옹이의 편식을 막기 위해 쿠옹이가 좋아하는 음식인 피자 위에 다양한 재료를 올리려고 한다. 이 피자는 첫 번째 조각과 마지막 조각이 연속되어 있는 원 모양이다.
쿠옹이의 피자의 선호도는 연속된 피자 조각의 피자 조각의 선호도의 합의 최댓값이다. 또한 피자 조각의 선호도는 그 피자 조각 위에 올라가 있는 재료의 재료의 선호도의 합과 같다. 아무 재료도 올라가 있지 않은 피자 조각의 선호도는 0이다.
아무 피자 조각도 선택하지 않고 피자의 선호도라고 하는 것은 이상하므로 피자의 선호도는 하나 이상의 피자 조각을 고르는 경우만을 포함한다.
최초에 피자 위에는 아무 재료도 올라가 있지 않다. 쿠옹이의 친구들은 총 Q번에 걸쳐 다음 두 행동 중 하나를 한다.
첫째 줄에 피자의 조각 수 S(1 ≤ S ≤ 200 000)와 쿠옹이의 친구들의 행동 수 Q(1 ≤ Q ≤ 500 000)가 공백으로 구분되어 주어진다.
이후 Q개의 줄에 걸쳐 행동이 주어진다.
행동 2는 적어도 한 번 이상 주어진다.
입력으로 주어지는 모든 수는 정수이다.
행동 2가 주어질 때마다 쿠옹이의 피자의 선호도를 출력하라.
5 121 1 31 2 31 3 -521 5 321 4 321 4 -521 3 42
6 9 12 9 9
