Consider integer sequence a₁, a₂, ..., a_n. You should run queries of two types:

• The query format is "0 i val". In reply to this query you should make the following assignment: a_i = val.
• The query format is "1 l r k". In reply to this query you should print the maximum sum of exactly k non-intersecting subsegments of sequence a_l, a_l + 1, ..., a_r. Formally, you should choose exactly k pairs of integers (x₁, y₁), (x₂, y₂), ..., (x_t, y_t) (l ≤ x₁ ≤ y₁ < x₂ ≤ y₂ < ... < x_t ≤ y_t ≤ r; t ≤ k) such that the sum a_x1 + a_x1 + 1 + ... + a_y1 + a_x2 + a_x2 + 1 + ... + a_y2 + ... + a_xt + a_xt + 1 + ... + a_ytis as large as possible.

Input

Output

Example

Input:
2
-1 -1
1
1 1 2 2
Output:
-2