#include <bits/stdc++.h>
using namespace std;

/**

9
5 2 8 3 9 7 1 4 6
      1 2 3 4 5 6 7 8 9
fr  = 0 1 1 0 1 0 0 1 0
aib[i] = suma elementelor din fr[i-2^k+1,i] (de lungime 2^k)
         unde k este numarul de biti de 0 cu care se termina i
         in baza 2

i   baza_2  intervalul  suma
1   0001    [1,1]       0
2   0010    [1,2]       1
3   0011    [3,3]       1
4   0100    [1,4]       2
5   0101    [5,5]       1
6   0110    [5,6]       1
7   0111    [7,7]       0   [1,7] = [7,7]+[5,6]+[1,4]
8   1000    [1,8]       4
9   1001    [9,9]       0
*/

ifstream fin("aib.in");
ofstream fout("aib.out");
int aib[100002], n, m;

/// ret. suma fr[1]+fr[2]+...+fr[p]
int Query(int p)
{
    int suma = 0;
    while (p > 0)
    {
        suma += aib[p];
        /// scadem din p valoarea 2^k
        p -= (p & (-p));
    }
    return suma;
}

/// aduna x la toate componentele aib[j] care-l contin pe p
void Update(int p, int x)
{
    while (p <= n)
    {
        aib[p] += x;
        p += (p & (-p));
    }
}

/// cauta cea mai din stanga poz p in care Query(p) = x
int CautBin(int x)
{
    int st,dr,mij,p,q;
    p=-1;
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        q=Query(mij);
        if(q==x)
        {
            p=mij;
            dr=mij-1;
        }
        else if(q<x)
            st=mij+1;
        else
            dr=mij-1;
    }
    return p;
}

int main()
{
    int i, x, op, y;
    fin >> n >> m;
    for (i = 1; i <= n; i++)
    {
        fin >> x;
        Update(i,x);
    }
    for(i=1;i<=m;i++)
    {
        fin>>op;
        if(op==0)
        {
            fin>>x>>y;
            Update(x,y);
        }
        else if(op==1)
        {
            fin>>x>>y;
            fout<<Query(y)-Query(x-1)<<'\n';
        }
        else
        {
            fin>>x;
            fout<<CautBin(x)<<'\n';
        }
    }
    return 0;
}