#include <bits/stdc++.h>

using namespace std;
ifstream fin ("aib.in");
ofstream fout ("aib.out");
int n,m,aib[100005],i,a,b,c,x;
void adun (int x, int val)
{
    int i;
    for(i=x ; i<=n ;i += i & (-i) )
        aib[i] += val;
}

int suma (int x)
{
    int i,s=0;
    for (i=x;i>=1;i-=i&(-i))
        s+=aib[i];
    return s;
}
int lb (int p)
{
    int i=p;
    while (i>0 && suma(i)==suma(p))
        i--;
    return i;
}
int cautbin (int x)
{
    int i,st,dr,mij;
    st=1;
    dr=n;
    while (st<=dr)
        {
            mij=st+(dr-st)/2;
            if (x>suma(mij))
                {
                    st=mij+1;
                }
            else if (x<suma(mij))
                {
                    dr=mij-1;
                }
            else
                {
                    return lb(mij);
                }
          if (suma(st)==x && st>0) return lb(mij);
        }
    return -1;
}
int main()
{
    fin>>n>>m;
    for (i=1;i<=n;i++)
        {
            fin>>x;
            adun(i,x);
        }
    while (m--)
        {
            fin>>c>>a;
            if (c==0)
                {
                    fin>>b;
                    adun(a,b);
                }
            if (c==1)
                {
                    fin>>b;
                    fout<<suma(b)-suma(a-1)<<"\n";
                }
            if (c==2)
                {
                    fout<<cautbin(a)<<"\n";
                }
        }
    return 0;
}