Sequence Operations and Maximum Subsequence Sum

Given a sequence of length (n): (a_1,a_2,\dots,a_n), you are to support two types of operations:

1. 1 k: Add an integer (k) to every element in the sequence.
2. 2: Query the maximum subsequence sum of the current sequence.

A subsequence is formed by deleting zero or more elements (but keeping the order of the remaining elements). Note that the empty subsequence is allowed and its sum is defined to be (0).

The maximum subsequence sum is computed by summing all elements that are positive (since you can choose an empty subsequence if all elements are non-positive).

inputFormat

The first line contains two integers (n) and (q), representing the length of the sequence and the number of operations, respectively.

The second line contains (n) integers: (a_1, a_2, \dots, a_n).

Each of the following (q) lines contains an operation in one of the following formats:
- 1 k: Add the integer (k) to every element of the sequence.
- 2: Query the maximum subsequence sum.

outputFormat

For each operation of type 2, output the maximum subsequence sum on a new line. The maximum subsequence sum is obtained by summing all values that are positive (or output (0) if none are positive).

sample

5 5
1 2 -3 4 -2
2
1 3
2
1 -2
2

7
17
10