#include <bits/stdc++.h>

using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
const int nmax = 100002;
void update(int poz, int val);
int query(int poz);
int cauta(int val);
int lsb(int x)
{
    return x & (-x);
}
int aib[nmax], n, m;

int main()
{
    fin>>n>>m;
    for(int i = 1; i <= n; ++i)
    {
        int nr;
        fin>>nr;
        update(i, nr);
    }
    while(m--)
    {
        int tip, a, b;
        fin>>tip>>a;
        if(tip == 0)
        {
            fin>>b;
            update(a, b);
        }
        else if(tip == 1)
        {
            fin>>b;
            fout<<query(b) - query(a-1)<<"\n";
        }
        else
            fout<<cauta(a)<<"\n";
    }





    return 0;
}
int cauta(int val)
{
    int poz = 0, scrt = 0, pas = 1;
    while(pas * 2 < n)
        pas = pas * 2;

    for(; pas >= 1; pas /= 2)
    {
        if(poz + pas <= n)
        {
            if(scrt + aib[poz+pas] < val)
            {
                scrt += aib[poz+pas];
                poz += pas;
            }
            else if(scrt + aib[poz+pas] == val)
                return poz + pas;
        }
    }
    return -1;

}

void update(int poz, int val)
{
    for(int i = poz; i <= n; i += lsb(i))
        aib[i] += val;
}
int query(int poz)
{
    int ans = 0;
    for(int i = poz; i >= 1; i -= lsb(i))
        ans += aib[i];
    return ans;
}