#include<cstdio>
using namespace std;
const int nmax=1e5+1;
int aib[nmax];
int n, m;

void update(int pos, int val)
{for(; pos<=n; pos+=(pos&(pos-1))^pos)
    aib[pos]+=val;
}

int querry(int pos)
{int s=0;
 for(; pos; pos-=(pos&(pos-1))^pos)
    s+=aib[pos];
 return s;
}

int search(int a, int b, int val)
{int med;
 while(a!=b)
    {med=(b-a)/2+a;
     if(querry(med)>=val)
        b=med;
     else a=med+1;
    }
 return a;
}

int main()
{freopen("aib.in", "r", stdin);
 freopen("aib.out", "w", stdout);
 scanf("%d%d", &n, &m);
 int i, op, a, b;
 for(i=1; i<=n; i++)
    {scanf("%d", &a);
     update(i, a);
    }
 for(i=1; i<=m; i++)
    {scanf("%d", &op);
     if(!op)
        {scanf("%d%d", &a, &b);
         update(a, b);
        }
     else if(op==1)
        {scanf("%d%d", &a, &b);
         printf("%d\n", querry(b)-querry(a-1));
        }
     else if(op==2)
        {scanf("%d", &a);
         printf("%d\n", search(1, n, a));
        }
    }
 return 0;
}