#include <iostream>
#include <fstream>
#define zeros(x) ((x^(x-1))&x)
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int aib[100005],n,m,op,a,b,d;

void add(int x,int y)
{
    for(int i=x;i<=n;i+=zeros(i))
    {
        aib[i]+=y;
    }
}

int compute(int x)
{
    int rez=0;
    for(int i=x;i>0;i-=zeros(i))
    {
        rez+=aib[i];
    }
    return rez;
}

int poz(int x)
{
    int lt=0,rt=n+1,md;
    while(rt-lt!=1)
    {
        md=(lt+rt)/2;
        d=compute(md);
        if(d==x) return md;
        if(d<x) lt=md;
        else rt=md;
    }
    return -1;
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=n;++i)
    {
        f>>a;
        add(i,a);
    }
    for(int i=1;i<=m;++i)
    {
        f>>op;
        if(op<2)
        {
            f>>a>>b;
            if(!op) add(a,b);
            else g<<(compute(b)-compute(a-1))<<'\n';
        }
        else
        {
            f>>a;
            g<<poz(a)<<'\n';
        }
    }
    return 0;
}