#include <bits/stdc++.h>

#define UB(x) (x&(-x))

using namespace std;

ifstream fin("aib.in");

ofstream fout("aib.out");

int n, m, a, b, aib[400005],x, p;

void add(int x, int val)
{
    for(int i=x;i<=n;i+=UB(i))

        aib[i]+=val;
}

int sum(int x)
{
    int s=0;

    for(int i=x;i>0;i-=UB(i))

        s+=aib[i];

    return s;
}

int cb(int x)
{
    int st=1, dr=n;

    while(st<=dr)
    {
        int mij=(st+dr)>>1;

        int s=sum(mij);

        if(x==s) return mij;

        if(x>s) st=mij+1;

        else dr=mij-1;
    }

    return -1;
}


int main()
{
   fin>>n>>m;

   for(int i=1;i<=n;++i)
   {
       fin>>x; add(i,x);
   }

   for(int i=1;i<=m;++i)
   {
       fin>>p;

       if(p==0)
       {
           fin>>a>>b;

           add(a,b);
       }

       else if(p==1)
       {
           fin>>a>>b;

           fout<<sum(b)-sum(a-1)<<'\n';
       }

       else
       {
           fin>>a;

           fout<<cb(a)<<'\n';
       }

   }


    return 0;
}