#include <iostream>
#include <fstream>
#define nmax 100005
using namespace std;

int aib[nmax], n, m, x, y;
inline int lbit(int x)
{
    return (x &(-x));
}
void update(int i, int val)
{
    for(i; i<=n; i+=lbit(i))
    {
        aib[i] += val;
    }

    return;
}

int find_sum(int i)
{
    int sum = 0;

    for(i; i>0; i-=lbit(i))
    {
        sum+=aib[i];
    }

    return sum;
}

int querry(int x, int y)
{
    x = find_sum(x-1);
    y = find_sum(y);
    return(y - x);
}

int cb(int st, int dr, int h)
{
    int mid;
    while (dr - st > 1)
    {
        mid = (st+dr)/2;

        if (h <= find_sum(mid)) dr = mid;
                           else st = mid;
    }

    if (dr <= n && find_sum(dr) == h) return dr;

    return -1;
}
int main()
{
    ifstream f("aib.in");
    ofstream g("aib.out");

    f >> n >> m;
    for(int i=1; i<=n; i++)
    {
        f >> x;
        update(i, x);
    }

    int act;
    for(int i=1; i<=m; i++)
    {
        f >> act;
        if(act == 0)
        {
            f >> x >> y;
            update(x, y);
        }else
        if (act == 1)
        {
            f >> x >> y;
            g << querry(x, y) << "\n";
        }else{
            f >> x;
            g << cb(0, n+1, x) <<"\n";
        }
    }


    f.close();
    g.close();
    return 0;
}