#include <fstream>
#include <vector>

using namespace std;

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

int n,m;
vector<int> x;


int asd(int a){
    return (a) & (-a);
}


void add(int k,int a){
    for(k=k;k<=n;k+=asd(k))
        x[k]+=a;
}

int sumtok(int k){
    int sum=0;
    for(k=k;k>0;k-=asd(k)){
        sum+=x[k];
    }
    return sum;
}

int intervalsum(int a, int b){
    return sumtok(b)-sumtok(a-1);
}

int binarysearch(int a){
    int first=1, last=n;
    int k;
    while(first<=last){
        k=(first+last)/2;
        if(a<sumtok(k)) last=k-1;
        else if(a>sumtok(k)) first=k+1;
        else break;
    }
    if(first<=last) return k;
    else return -1;
}

int main()
{
    fin>>n>>m;
    x.resize(n+1);
    int f,g,h;
    for(int i=1;i<=n;i++){
        fin>>f;
        add(i,f);
    }
    for(int i=1;i<=m;i++){
        fin>>h;
        if(h==0){
            fin>>f>>g;
            add(f,g);
        }
        else if(h==1){
            fin>>f>>g;
            fout<<intervalsum(f,g)<<"\n";
        }
        else if(h==2){
            fin>>f;
            fout<<binarysearch(f)<<"\n";
        }
    }
    return 0;
}