/*#include <iostream>
#include <cstdio>

const char inFile[] = "datorii.in";
const char outFile[] = "datorii.out";
const int NMAX = 15002;

using namespace std;

int arb[5 * NMAX], n, m, value, target, sum, intl, intr;

void update(int nod, int left, int right) {
    if(left == right) {
        arb[nod] = value;
        return;
    }

    int mid = (left + right) / 2;
    if(mid >= target)
        update(nod * 2, left, mid);
    else
        update(nod * 2 + 1, mid + 1, right);
    arb[nod] = max(arb[nod * 2], arb[nod * 2 + 1]);
}

void pay(int nod, int left, int right) {
    if(left == right) {
        arb[nod] -= value;
        return;
    }

    int mid = (left + right) / 2;
    if(mid >= target)
        pay(nod * 2, left, mid);
    else
        pay(nod * 2 + 1, mid + 1, right);
    arb[nod] = max(arb[nod * 2], arb[nod * 2 + 1]);
}

void genMax(int nod, int left, int right) {
    if(left == intl && right == intr) {
        sum = arb[nod];
        return;
    }

    int mid = (left + right) / 2;
    if(mid >= intl)
        genMax(nod * 2, left, mid);
    if(mid < intr)
        genMax(nod * 2 + 1, mid + 1, right);
}

int main()
{
    int x, a, b;
    freopen(inFile, "r", stdin);
    freopen(outFile, "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &x);
        target = i, value = x;
        update(1, 1, n);
    }
    for(int i = 1; i <= m; ++i) {
        scanf("%d %d %d", &x, &a, &b);
        if(x == 0) {
            target = a, value = b;
            pay(1, 1, n);
        }
        else {
            intl = a, intr = b, sum = 0;
            genMax(1, 1, n);
            printf("%d\n", sum);
        }
    }
}*/
#include <iostream>
#include <cstdio>

const char inFile[] = "datorii.in";
const char outFile[] = "datorii.out";
const int NMAX = 15002;

using namespace std;

int arb[5 * NMAX], n, m, value, target, sum, intl, intr;

void update(int nod, int left, int right) {
    if(left == right) {
        arb[nod] = value;
        return;
    }

    int mid = (left + right) / 2;
    if(mid >= target)
        update(nod * 2, left, mid);
    else
        update(nod * 2 + 1, mid + 1, right);
    arb[nod] = arb[nod * 2] + arb[nod * 2 + 1];
}

void pay(int nod, int left, int right) {
    if(left == right) {
        arb[nod] -= value;
        return;
    }

    int mid = (left + right) / 2;
    if(mid >= target)
        pay(nod * 2, left, mid);
    else
        pay(nod * 2 + 1, mid + 1, right);
    arb[nod] = arb[nod * 2] + arb[nod * 2 + 1];
}

void genMax(int nod, int left, int right) {
    if(left >= intl && right <= intr) {
        if(sum < arb[nod]) sum += arb[nod];
        return;
    }

    int mid = (left + right) / 2;
    if(mid >= intl)
        genMax(nod * 2, left, mid);
    if(mid < intr)
        genMax(nod * 2 + 1, mid + 1, right);
}

int main()
{
    int x, a, b;
    freopen(inFile, "r", stdin);
    freopen(outFile, "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &x);
        target = i, value = x;
        update(1, 1, n);
    }
    for(int i = 1; i <= m; ++i) {
        scanf("%d %d %d", &x, &a, &b);
        if(x == 0) {
            target = a, value = b;
            pay(1, 1, n);
        }
        else {
            intl = a, intr = b, sum = 0;
            genMax(1, 1, n);
            printf("%d\n", sum);
        }
    }
}