The first line contains integer *n* (1 ≤ *n* ≤ 10^{5}), showing how many numbers the sequence has. The next line contains *n* integers *a*_{1}, *a*_{2}, ..., *a*_{n} (|*a*_{i}| ≤ 500).

The third line contains integer *m* (1 ≤ *m* ≤ 10^{5}) — 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.