#include <iostream>
#include <cstdio>
#define N 100005

using namespace std;

int x, n, m, s[N], a, b;

void update(int i, int val)
{
    while(i<=n)
    {
        s[i]+=val;
        i+=((i^(i-1))&i);
    }
}

void citire()
{
    scanf("%d %d\n", &n, &m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d ", &x);
        update(i, x);
    }
}

int caut(int x)
{
    int st=1, dr=n, poz=-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(s[mij]==x)
        {
            poz=mij;
            dr=mij-1;
        }
        if(s[mij]<x)
            st=mij+1;
        else
            dr=mij-1;
    }
    return poz;
}

int main()
{
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);

    citire();
    for(int pas=0;pas<m;pas++)
    {
        scanf("%d %d ", &x, &a);
        if(x!=2)
            scanf("%d\n", &b);
        else
            scanf("\n");
        switch(x)
        {
            case 0: update(a, b); break;
            case 1: if(a!=b)
                        printf("%d\n", s[b]-s[a-1]);
                    else
                        printf("%d\n", s[b]); break;
            case 2: printf("%d\n", caut(a)); break;
        }
    }

    for(int i=1;i<=n;i++)
        printf("%d ", s[i]);
    return 0;
}