#include <cstdio>
#include <fstream>
#define DIM 100010

using namespace std;

int n, m;
int aib[DIM];

int Query1(int poz)
{
    int sum = 0;
    for (;poz > 0;poz -= poz & (-poz))
        sum += aib[poz];
    return sum;
}

int Query2(int a)
{
    int left = 1, right = n, mid;
    int poz = -1;
    while(left <= right)
    {
        mid = (left + right) / 2;
        int rez = Query1(mid);
        if(rez == a)
        {
            poz = mid;
            right = mid - 1;
        }
        else
        {
            if (rez > a)
                right = mid - 1;
            else
                left = mid + 1;
        }
    }
    return poz;
}

void Update(int poz, int val)
{
    while(poz <= n)
    {
        aib[poz] += val;
        poz += poz & (-poz);
    }
}

int main()
{
    FILE *f = fopen("aib.in", "r");
    FILE *g = fopen("aib.out", "w");
    //ifstream f("aib.in");
    //ofstream g("aib.out");
    fscanf(f, "%d %d", &n, &m);
    //f >> n >> m;
    for (int i = 1;i <= n;++i)
    {
        //f >> a[i];
        int x;
        fscanf(f, "%d", &x);
        Update(i, x);
    }
    for (int i = 1;i <= m;++i)
    {
        int cod;
        //f >> cod;
        fscanf(f, "%d", &cod);
        switch(cod)
        {
            case 0:
            {
                int poz, val;
                //f >> poz >> val;
                fscanf(f, "%d %d", &poz, &val);
                Update(poz, val);
                break;
            }
            case 1:
            {
                int x, y;
                //f >> x >> y;
                fscanf(f, "%d %d", &x, &y);
                x = Query1(x - 1);
                y = Query1(y);
                //g << y - x << "\n";
                fprintf(g, "%d\n", y - x);
                break;
            }
            case 2:
            {
                int k;
                //f >> k;
                fscanf(f, "%d", &k);
                //g << Query2(k) << "\n";
                fprintf(g, "%d\n", Query2(k));
                break;
            }
        }
    }
    //f.close();
    //g.close();
    fclose(f);
    fclose(g);
    return 0;
}