#include <fstream>

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

#define f(x) ((x^(x-1))&x)
const int nmax=100000;
int n,q;
int aib[nmax+5];

void add(int poz,int quantity)
{
    for(int i=poz;i<=n;i+=f(i))
        aib[i]+=quantity;
}
int prefix(int poz)
{
    int ans=0;
    for(int i=poz;i>=1;i-=f(i))
        ans+=aib[i];
    return ans;
}
int main()
{
    fin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        int key;
        fin>>key;
        add(i,key);
    }
    while(q--)
    {
        int tip,a,b;
        fin>>tip>>a;
        if(tip!=2)
            fin>>b;
        if(tip==0)
            add(a,b);
        if(tip==1)
            fout<<prefix(b)-prefix(a-1)<<"\n";
        if(tip==2)
        {
            int r=0,pas=(1<<16);
            while(pas)
            {
                if(r+pas<=n && prefix(r+pas)<a)
                    r+=pas;
                pas/=2;
            }
            r++;
            if(r<=n && prefix(r)==a)
                fout<<r<<"\n";
            else
                fout<<"-1\n";
        }
    }
    return 0;
}
/**
**/