#include <bits/stdc++.h>

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

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

const int NMAX = 100000;

int a[NMAX+5];
int n,m;

void Add(int poz,int value) {
    for (int i=poz; i<=n; i+=ub(i))
        a[i]+=value;
}

int Sum(int poz) {
    int sum=0;
    for (int i=poz; i>0; i-=ub(i))
        sum+=a[i];

    return sum;
}

int BinarySearch(int x) {
    int st=1,dr=n,mij;
    while (st<=dr) {
        mij=(st+dr)/2;
        int s=Sum(mij);

        if (s==x) return mij;
        else
        if (s<x) st=mij+1;
        else dr=mij-1;
    }

    return -1;
}
int main()
{
    fin>>n>>m;
    for (int i=1; i<=n; i++) {
        int x;
        fin>>x;
        Add(i,x);
    }

    while (m--) {
        int tip,a,b;
        fin>>tip;

        switch (tip) {
        case 0:
            fin>>a>>b;
            Add(a,b);
            break;
        case 1:
            fin>>a>>b;
            fout<<Sum(b)-Sum(a-1)<<'\n';
            break;
        case 2:
            fin>>a;
            fout<<BinarySearch(a)<<'\n';
            break;
        }
    }
    return 0;
}