#include<cstdio>
#define NMAX 100001
using namespace std;
int aib[NMAX],n;
void update(int val, int poz)
{
    for(; poz<=n; poz+=poz&(poz-1)^poz)
        aib[poz]+=val;
}
int query(int day1, int day2)
{
    day1-=1;
    int s=0;
    for(; day2; day2-=day2&(day2-1)^day2)
        s+=aib[day2];
    for(; day1; day1-=day1&(day1-1)^day1)
        s-=aib[day1];
    return s;
}
int binarysearch(int left,int right, int a)
{
    int mid;
    while(left!=right)
    {
        mid =(left+right)>>1;
        if(aib[mid]==a)
            return mid;
        else if(aib[mid]>a)
            right=mid;
        else
            left=mid+1;
    }
}
int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    int m,i,sum,operation,day1,day2;
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; ++i)
    {
        scanf("%d",&sum);
        update(sum,i);
    }
    for(i=1; i<=m; ++i)
    {
        scanf("%d",&operation);
        switch(operation)
        {
        case 0 :
            scanf("%d%d",&day1,&sum);
            update(sum,day1);
            break;
        case 1 :
            scanf("%d%d",&day1,&day2);
            printf("%d\n",query(day1,day2));
            break;
        case 2 :
            scanf("%d",&sum);
            printf("%d\n",binarysearch(1,n,sum));
            break;
        }

    }
    return 0;

}