#include <bits/stdc++.h>

using namespace std;

ifstream inf("aib.in");
ofstream outf("aib.out");

int n, m, v[100010], aib[100010];

void aib_add(int ,int );
int aib_get(int ), tcomp(int ), aib_search(int ,int ,int );

int main()
{
    inf>>n>>m;
    for(int i=1; i<=n; i++)
        inf>>v[i],aib_add(i, v[i]);
    for(;m;m--)
    {
        int tip, a, b;
        inf>>tip;
        if(tip==0)
        {
            inf>>a>>b;
            aib_add(a,b);
        }
        else if(tip==1)
        {
            inf>>a>>b;
            outf<<aib_get(b)-aib_get(a-1)<<'\n';
        }
        else
        {
            inf>>a;
            outf<<aib_search(1,n,a)<<'\n';
        }
    }
    return 0;
}

int tcomp(int a)
{
    return (~a)+1;
}

void aib_add(int ind, int val)
{
    int nxt=ind+(ind&tcomp(ind));
    aib[ind]+=val;
    while(nxt<=n)
    {
        aib[nxt]+=val;
        nxt=nxt+(nxt&tcomp(nxt));
    }

}

int aib_get(int ind)
{
    int curr=ind, ret=0;
    while(curr>0)
    {
        ret+=aib[curr];
        curr=curr-(curr&tcomp(curr));
    }
    return ret;
}

int aib_search(int st, int dr, int val)
{
    if(st>dr)
        return -1;
    int m=(st+dr)/2, q=aib_get(m);
    if(q==val)
    {
        int aux=aib_search(st,m-1,val);
        if(aux>0)
            return aux;
        else
            return m;
    }
    else
    {
        if(q>val)
            return aib_search(st, m-1, val);
        else
            return aib_search(m+1, dr, val);
    }
}