#include<bits/stdc++.h>
#define zeros(x) ((x^(x-1))&x)
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n,m,nr,AIB[100002];
int op,poz,val;
void Add(int x, int quantity)
{
    int i;

    for (i = x; i <= n; i += zeros(i))
        AIB[i] += quantity;
}
int Compute(int x)
{
    int i, ret = 0;

    for (i = x; i > 0; i -= zeros(i))
        ret += AIB[i];
    return ret;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;++i)
    {
        f>>nr;
        Add(i,nr);
    }
    for(int i=1;i<=m;++i)
    {
        f>>op>>poz;
        if(op==0){
            f>>val;
            Add(poz,val);
        }
        if(op==1){
            f>>val;
            g<<Compute(val)-Compute(poz-1)<<'\n';
        }
        if(op==2)
        {
            int b=0;
            int e=n;
            bool ok=0;
            while(b<=e)
            {
                int m=(b+e)/2;
                if(Compute(m)==poz){
                    g<<m<<'\n';
                    ok=1;
                    break;
                }
                else
                    if(Compute(m)>poz)
                        e=m-1;
                    else
                        b=m+1;
            }
            if(ok==0)
                g<<-1<<'\n';
        }
    }
    return 0;
}