#include <bits/stdc++.h>
#define MAX 100005

using namespace std;

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

int aib[MAX];
int n,m;

int ub(int x)
{
    return (x & (-x));
}

void add(int x,int val)
{
    int i;
    for(i=x;i<=n;i+=ub(i))
        aib[i]+=val;
}

int sum(int x)
{
    int rez=0;
    int i;
    for(i=x;i;i-=ub(i))
        rez+=aib[i];
    return rez;
}

int main()
{
    fin>>n>>m;
    int i;
    for(i=1;i<=n;++i)
    {
        int nr;
        fin>>nr;
        add(i,nr);
    }
    while(m--)
    {
        int tip;
        fin>>tip;
        if(tip==0)
        {
            int a,b;
            fin>>a>>b;
            add(a,b);
        }
        else
            if(tip==1)
            {
                int a,b;
                fin>>a>>b;
                fout<<sum(b)-sum(a-1)<<'\n';
            }
            else
            {
                int a;
                fin>>a;
                int rasp=-1;
                int st=1,dr=n;
                while(st<=dr)
                {
                    int mij=(st+dr)/2;
                    int s=sum(mij);
                    if(s==a)
                    {
                        rasp=mij;
                        dr=mij-1;
                    }
                    else
                        if(s<a)
                            st=mij+1;
                        else
                            dr=mij-1;
                }
                fout<<rasp<<'\n';
            }
    }
    return 0;
}