human
Can you solve the below in CPP?
Consider integer sequence a1, a2, ..., an. 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: ai = val. 
  * The query format is "1 l r k". In reply to this query you should print the maximum sum of at most k non-intersecting subsegments of sequence al, al + 1, ..., ar. Formally, you should choose at most k pairs of integers (x1, y1), (x2, y2), ..., (xt, yt) (l ≤ x1 ≤ y1 < x2 ≤ y2 < ... < xt ≤ yt ≤ r.
t ≤ k) such that the sum ax1 + ax1 + 1 + ... + ay1 + ax2 + ax2 + 1 + ... + ay2 + ... + axt + axt + 1 + ... + ayt is as large as possible. Note that you should choose at most k subsegments. Particularly, you can choose 0 subsegments. In this case the described sum considered equal to zero. 

Input

The first line contains integer n (1 ≤ n ≤ 105), showing how many numbers the sequence has. The next line contains n integers a1, a2, ..., an (|ai| ≤ 500). 

The third line contains integer m (1 ≤ m ≤ 105) — the number of queries. The next m lines contain the queries in the format, given in the statement.

All changing queries fit into limits: 1 ≤ i ≤ n, |val| ≤ 500.

All queries to count the maximum sum of at most k non-intersecting subsegments fit into limits: 1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ 20. It is guaranteed that the number of the queries to count the maximum sum of at most k non-intersecting subsegments doesn't exceed 10000.

Output

For each query to count the maximum sum of at most k non-intersecting subsegments print the reply — the maximum sum. Print the answers to the queries in the order, in which the queries follow in the input.

Examples

Input

9
9 -8 9 -1 -1 -1 9 -8 9
3
1 1 9 1
1 1 9 2
1 4 6 3

Output

17
25
0

Input

15
-4 8 -3 -10 10 4 -7 -7 0 -6 3 8 -10 7 2
15
1 3 9 2
1 6 12 1
0 6 5
0 10 -7
1 4 9 1
1 7 9 1
0 10 -3
1 4 10 2
1 3 13 2
1 4 11 2
0 15 -9
0 13 -9
0 11 -10
1 5 14 2
1 6 12 1

Output

14
11
15
0
15
26
18
23
8

Note

In the first query of the first example you can select a single pair (1, 9). So the described sum...
assistant
#Here is Python code to print the answers to the queries in the order, in which the queries follow in the input.

#include <bits/stdc++.h>
#pragma warning(disable : 4996)
#pragma warning(disable : 6031)
namespace def {}
namespace tydef {}
namespace io {
const int SIZ = 1 << 21 | 1;
char *iS, *iT, ibuff[SIZ], obuff[SIZ], *oS = obuff, *oT = oS + SIZ - 1, fu[110],
                                       c;
int fr;
inline void out() {
  fwrite(obuff, 1, oS - obuff, stdout);
  oS = obuff;
}
template <class Type>
inline void read(Type& x) {
  x = 0;
  Type y = 1;
  for (c = (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       (c > '9' || c < '0') && c != '-';
       c = (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    ;
  c == '-' ? y = -1 : x = (c & 15);
  for (c = (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++);
       c >= '0' && c <= '9';
       c = (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = x * 10 + (c & 15);
  x *= y;
}
template <class Type>
inline void print(Type x, char text = '\n') {
  if (x < 0) *oS++ = '-', x *= -1;
  if (x == 0) *oS++ = '0';
  while (x) fu[++fr] = x % 10 + '0', x /= 10;
  while (fr) *oS++ = fu[fr--];
  *oS++ = text;
  out();
}
inline void prints(char x[], char text = '\n') {
  for (register int i = 0; x[i]; ++i) *oS++ = x[i];
  *oS++ = text;
  out();
}
}  // namespace io
using namespace tydef;
const int MAX_prime = 0;
namespace Fa {
template <class Type>
inline Type fact(Type n) {
  static Type Fact[55];
  if (n == 1) return Fact[n] = 1;
  if (!Fact[n])
    return Fact[n] = n * fact(n - 1);
  else
    return Fact[n];
}
template <class Type>
inline Type gcd(Type x, Type y) {
  while (x ^= y ^= x ^= y %= x)
    ;
  return y;
}
template <class Type>
Type power(Type x, Type y) {
  Type ans = 1;
  while (y) {
    if (y...