B"Consider integer sequence a1, xe2 x80 x89a2, xe2 x80 x89..., xe2 x80 x89an. You should run queries of two types: The first line contains integer n (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89105), showing how many numbers the sequence has. The next line contains n integers a1, xe2 x80 x89a2, xe2 x80 x89..., xe2 x80 x89an (|ai| xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89500). The third line contains integer m (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89m xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89105) -- 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 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89i xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n, |val| xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89500. All queries to count the maximum sum of at most k non-intersecting subsegments fit into limits: 1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89l xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89r xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n, 1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89k xe2 x80 x89 xe2 x89 xa4 xe2 x80 x8920. 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. 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. In the first query of the first example you can select a single pair (1, xe2 x80 x899). So the described sum will be 17. Look at the second query of the first example. How to choose two subsegments? (1, 3) and (7, 9)? Definitely not, the sum we could get from (1, 3) and (7, 9) is 20, against the optimal configuration (1, 7) and (9, 9) with 25. The answer to the third query is 0, we prefer select nothing if all of the numbers in the given interval are negative."...