#include<fstream>
#include<iostream>
using namespace std;
#define MAX 100001
 
int N,M,bit[MAX];
 
ifstream in("aib.in");
ofstream out("aib.out");
 
void update(int p,int val)
{
    int ind=p;
    while(ind<=N)
    {
        bit[ind]+=val;
        ind +=ind&(-ind);
    }
}
int getSum(int e)
{
    int ind=e,s=0;
    while(ind>0)
    {
        s+=bit[ind];
        ind-=ind&(-ind);
    }
    return s;
}
 
int minK(int a)
{
    int st=1,dr=N,mid,k;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        k=getSum(mid);
        if(k==a)
            return mid;
        else if(a<k)
            dr=mid-1;
        else
            st=mid+1;
    }
    return -1;
}
int main()
{
    in>>N>>M;
    int op,a,b;
    for(int i=1;i<=N;i++)
    {
        in>>a;
        update(i,a);
    }
    for(int j=1;j<=M;j++)
    {
        in>>op;
        switch(op)
        {
        case 0:
            in>>a>>b;
            update(a,b);
            break;
        case 1:
            in>>a>>b;
            out<<getSum(b)-getSum(a-1)<<'\n';
            break;
        case 2:
            in>>a;
            out<<minK(a)<<'\n';
            break;
        }
    }
    return 0;
}