#include <iostream>
#include <fstream>

using namespace std;
ifstream fin ("aib.in");
ofstream fout ("aib.out");
int n, m;
int aib[100010];

int zeros(int x)
{
    return (x&(-x));
}
void add (int poz, int x)
{
    for(int j=poz; j<=n; j+=zeros(j))
            aib[j]+=x;
}
int sum_cu_1 (int a)
{
    int rez=0;
    while(a)
    {
        int z=zeros(a);
        rez+=aib[a];
        a-=z;
    }
    return rez;
}
int sum_interval (int a, int b)
{
    return sum_cu_1(b)-sum_cu_1(a-1);
}
int caut_binar_k (int sum)
{
    int st=1, dr=n;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        int s=sum_cu_1(mid);
        if(s==sum)
            return mid;
        else if(s>sum)
            dr=mid-1;
        else st=mid+1;
    }
    return -1;
}
int main()
{
    fin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        int x;
        fin>>x;
        add(i, x);
    }
    for(int i=1; i<=m; i++)
    {
        int tip, a, b;
        fin>>tip;
        if(tip==0)
        {
            fin>>a>>b;
            add(a, b);
        }else
        if(tip==1)
        {
            fin>>a>>b;
            fout<<sum_interval(a,b)<<"\n";
        }else{
            fin>>a;
            fout<<caut_binar_k(a)<<"\n";
        }
    }
    return 0;
}