#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>


using namespace std;
inline int lsb(int x) {
    return x & (-x);
}
int n,c[100007];
ifstream f("aib.in");
ofstream g("aib.out");

int m,p,q,a,x;
void aduna(int ind, int val)
{
    for(int i=ind; i<=n; i+=lsb(i))
        c[i]+=val;
}
int suma(int dr)
{
    int s=0;
   for(int i=dr; i>0; i-=lsb(i))
    s+=c[i];
    return s;


}
int caut(int x)
{
    int st = 1, dr = n, ans = -1;
    while(st <= dr) {
        int mid = ((st + dr) >> 1);
        int q = suma(mid);
        if(q == x) {
            ans = mid;
            dr = mid - 1;
        }
        if(q > x)
            dr = mid - 1;
        else
            st = mid + 1;
    }
    return ans;
}
int main()
{
    f>>n>>m;
    for(int i=1; i<=n; i++)
        {
            f>>x;
            aduna(i,x);
        }
    for(int i=1; i<=m; i++)
    {
        f>>x;
        if(x==0)
            {
                f>>p>>q;
                aduna(p,q);
            }
        if(x==1)
        {
            f>>p>>q;
            g<<suma(q)-suma(p-1)<<"\n";
        }
        if(x==2)
        {
            f>>a;
            g<<caut(a)<<"\n";
        }
    }
    return 0;
}