#include <stdio.h>
#define pas (k^(k-1))&k

int n, m, a[100001];

void recreate(int k, int val)
{
    while (k<=n)
        {
            a[k]+=val;
            k+=pas;
        }
}

int sum(int k)
{
    int s=0;
    while (k>0)
       {
           s+=a[k];
           k-=pas;
       }
    return s;
}

int seesum(int a)
{
    int mij, st, dr;
    mij=n >> 1;
    st=1;
    dr=n;
    while (st<dr)
        {
            if (sum(mij)==a) return mij;
            else
                if (sum(mij)>a)
                    {
                        dr=mij;
                        mij=(dr+st)>>1;
                    }
                else
                    {
                        st=mij;
                        mij=(dr+st)>>1;
                    }
        }
    return -1;
}

void parc()
{
    int a, b, x;
    while (m>0)
        {
            scanf("%d", &x);
            if (x==0)
                {
                    scanf("%d" "%d", &a, &b);
                    recreate(a,b);
                }
            if (x==1)
                {
                    scanf("%d" "%d", &a, &b);
                    printf("%d\n", sum(b)-sum(a-1));
                }
            if (x==2)
                {
                    scanf("%d", &a);
                    printf("%d\n", seesum(a));
                }
            m--;
        }
}

void readit()
{
    int val, i;
    scanf("%d" "%d", &n, &m);
    for (i=1; i<=n; i++)
        {
            scanf("%d", &val);
            recreate(i,val);
        }
}

int main()
{
    int i;
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
    readit();
    parc();
    return 0;
}