#include <iostream>
#include <stdio.h>
#include <cmath>
#include <vector>

int main() {
	FILE *in = fopen("arbint.in", "r");
	FILE *out = fopen("arbint.out", "w");

	int N, M;
	fscanf(in, "%d %d", &N, &M);

	std::vector<int> A;
	for (int i = 0; i < N; i++) {
		int val;
		fscanf(in, "%d", &val);
		A.push_back(val);
	}

	int square = std::sqrt(N);
	std::vector<int> B;
	for (int i = 0; i < square; i++) {
		int sum = 0;
		for (int j = i * square; j < (i * square) + square; j++) {
			sum += A[j];
		}
		B.push_back(sum);
	}

	if (N % square != 0) {
		int sum = 0;
		for (int i = N; i >= N - (N % square); i--) {
			sum += A[i];
		}
		B.push_back(sum);
	}

	for (int i = 0; i < M; i++) {
		int op, a, b;
		fscanf(in, "%d %d %d", &op, &a, &b);
		a = a - 1;
		if (op == 1) {
			int dif = b - A[a];
			A[a] = b;
			B[a / square] += dif;
		} else {
			b = b - 1;
			int maxVal = 0;
			for (int i = a/square + 1; i < b/square; i++) {
				if (B[i] > maxVal)
					maxVal = B[i];
			}
			for (int i = (a/square + 1)*square - 1; i >= a; i--) {
				if (A[i] > maxVal)
					maxVal = A[i];
			}
			for (int i = (b/square)*square; i <= b; i++) {
				if (A[i] > maxVal)
					maxVal = A[i];
			}
			fprintf(out, "%d\n", maxVal);
		}
	}

	fclose(in);
	fclose(out);
	return 0;
}