#include <bits/stdc++.h>
#define ub(x) (x&(-x))

using namespace std;

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

const int NMAX=1e5+5;
int n, m, aib[NMAX];

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

int query (int poz)
{
    int s=0;
    for (int i=poz; i>=1; i-=ub(i))
        s+=aib[i];
    return s;
}

int cb (int n, int val)
{
    int st=1, dr=n;
    while (st<=dr)
    {
        int mij=(st+dr)/2;
        if (query(mij)>val)
            dr=mij-1;
        else if (query(mij)<val)
            st=mij+1;
        else
            return mij;
    }
    return -1;
}

int main()
{
    fin >> n >> m;
    for (int i=1; i<=n; i++)
    {
        int x;
        fin >> x;
        update(i,x);
    }
    for (int i=1; i<=m; i++)
    {
        int c, a, b;
        fin >> c >> a;
        if (c==0)
        {
            fin >> b;
            update(a,b);
        }
        else if (c==1)
        {
            fin >> b;
            fout << query(b)-query(a-1) << '\n';
        }
        else
            fout << cb(n,a) << '\n';
    }
    return 0;
}