#include<cstdio>
#define aibSIZE 100000
using namespace std;

int aib[aibSIZE + 1], n, m;

inline void updateAIB(int val, int pos)
{
    while(pos <= n)
    {
        aib[pos] += val;
        pos += pos & -pos;
    }
}

inline int sum(int x)
{
    int s = 0;
    while(x)
    {
        s += aib[x];
        x &= (x - 1);
    }
    return s;
}

int Bsearch(int x)
{
   int left, right, mid, suma;
   left = 1; right = n;
   while(left <= right)
   {
       mid = (left + right) >> 1;
       suma = sum(mid);
       if(suma == x)
            return mid;
       else if(x > suma)
            left = mid + 1;
       else right = mid - 1;
   }
   return -1;
}

int main()
{
    int op, a, b, i;
    FILE *fin, *fout;
    fin = fopen("aib.in","r");
    fout = fopen("aib.out","w");
    fscanf(fin,"%d%d",&n,&m);
    for(i=1; i<=n; i++)
    {
        fscanf(fin,"%d",&a);
        updateAIB(a,i);
    }
    for(i=1; i<=m; i++)
    {
        fscanf(fin,"%d%d",&op,&a);
        if(op != 2) fscanf(fin,"%d",&b);
        if(op == 0)
            updateAIB(b,a);
        else if(op == 1)
            fprintf(fout,"%d\n",sum(b) - sum(a-1));
        else fprintf(fout,"%d\n",Bsearch(a));
    }
    fclose(fin);
    fclose(fout);
    return 0;
}