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

int aib[MAXN];
int n,m;

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

int nrZerouri(int x)
{
    return (x&(-x));
}

void adaugare(int valoare, int poz)
{
    int pozitie=poz;
    while(pozitie<=n)
    {
        aib[pozitie]+=valoare;
        pozitie+=nrZerouri(pozitie);
    }
}

long long int suma(int x, int y)
{
    if(y<=0)
        return 0;
    if(x!=1)
        return suma(1,y)-suma(1,x-1);
    return aib[y]+suma(1,y-nrZerouri(y));
}
int cautbin(int val)
{
    int st=1, dr=n;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(aib[mij]==val)
            return mij;
        if(aib[mij]<val)
            st=mij+1;
        else
            dr=mij;
    }
    return -1;
}
void citire()
{
    fin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        int x;
        fin>>x;
        adaugare(x,i);
    }
    int op;
    for(int i=0;i<m;i++)
    {
        fin>>op;
        if(op==0)
        {
            int x,y;
            fin>>x>>y;
            adaugare(y,x);
        }
        if(op==1)
        {
            int x,y;
            fin>>x>>y;
            fout<<suma(x,y)<<"\n";
        }
        if(op==2)
        {
            int x;
            fin>>x;
            int poz=cautbin(x);
            fout<<poz<<"\n";
        }
    }
}
int main()
{
    citire();
    return 0;
}