/* arbori indexati binari


la arbori indexati binari se cauta ultimul numar cu un singur nr de biti de 1 si se aduna tot pana acolo.


i & -i - important pentru izolarea ultimului bit
i= 10110100
-i=01001100
i& -i = 00000100

1010 = 10 => 1100 = 12

i+=(i & -i)   10110100 -> 10111000 -> 1100000... se muta unu pe primul zero

i-=(i & -i) eliminam un 1 pe ultima pozitie

i-=(i&-i) = > query

i-> i+=(i&-i) => update parcurgi arborele


3-> 0011
4-> 0100
8-> 1000

suma primelor 13 -> suma [13,13]

1101=13
query 
1100=12 ->suma [9,12];
query
1000=8 ->suma[1,8];

*/
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("aib.in");
ofstream fout ("aib.out");

const int nmax=100001;
int n,m,x,a,b,opp;
int aib[nmax];

void update(int i, int x) // j+=(j&-j) ->
// trecem prin numerele care il contin in suma pe elementul de pe pozitia i
{
    for(int j=i;j<=n;j+=(j&-j))
    {
        aib[j]+=x;
    }
}
void create()
{
    for(int i=1;i<=n;i++)
    {
        fin>>x;
        update(i,x);
    }
}
int query(int i)
{
    int s=0;
    for(int j=i;j>=1;j-=(j&-j))
     // j -= (j&-j) -> eliminam cel mai din dreapta bit de 1 la fiecare pas, j&(-j) reprezinta cel mai din dreapta bit de 1, putem sa il 
    ///eliminam deoarece j contine exact suma a j&(-j) elemente, 
    ///deci cu exact atatea elemente mergem in spate
    {
        s+=aib[j];
    }
    return s;
}

int posmin(int a)
{
    int st=1,dr=n;
    int sol=-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        int k=query(mij);
        if(k==a) sol=mij;
        if(k>=a) dr=mij-1;
        else
            st=mij+1;
    }
    return sol;
}

int main()
{
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
    fin >> n >> m ;
    create();
    for(int i=1;i<=m;i++)
    {
        fin >> opp;
        switch(opp)
        {
            case 0:
                fin>>a>>b;
                update(a,b);
                break;
            case 1:
                fin >> a >> b;
                fout << query(b) - query(a-1) << "\n";
                break;
            case 2:
                fin >> a;
                fout << posmin(a) <<'\n';
                break;
        }
    }
}