#include <bits/stdc++.h>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
const int N = 100010;
int n,aib[N],m,tip,a,b;
int suma(int poz)
{
    int ret=0;
    for(int i=poz;i>0;i-=i&(-i))
        ret+=aib[i];
    return ret;
}
int suma(int st,int dr)
{
    return suma(dr)-suma(st-1);
}
void aduna(int poz,int val)
{
    for(int i=poz;i<=n;i+=i&(-i))
        aib[i]+=val;
}
int cautBin(int sum)
{
    int lo=0,hi=n;
    while(hi-lo>1)
    {
        int mi=(lo+hi)/2;
        if(suma(mi)<sum)
            lo=mi;
        else
            hi=mi;
    }
    if(suma(hi)==sum)
        return hi;
    return -1;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        f>>a;
        aduna(i,a);
    }
    for(int i=1;i<=m;i++)
    {
        f>>tip>>a;
        if(tip==0)
        {
            f>>b;
            aduna(a,b);
        }
        else if(tip==1)
        {
            f>>b;
            g<<suma(a,b)<<'\n';
        }
        else
            g<<cautBin(a)<<'\n';
    }
    return 0;
}
//
//AIB = vector care memoreaza in mod convenabil sume pe secvente
//
// 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 ......
//[]  | []  | []  | []    []  | []  | []  | []    []  | []  | []  |     bit inferior = 1 (2k+1) (1,3,5,7,...)
//[___]     | [___]       [___]     | [___]       [___]     | [___]     bit inferior = 2 (4k+2) (2,6,10,14,...)
//[_________]             [_________]             [_________]           bit inferior = 4 (8k+4) (4,12,20,28,36,...)
//[_____________________]                                               bit inferior = 8 (16k+8)(8,24,40,56,72,...)
//[______________________________________________]                      bit infrior  = 16 (32k+16)(16,48,80,112,...)
//                                                                                     32 (32,96,160,....)
//
//
//suma pana la o pozitie i ->
//    de ce forma este i? < ce bit inferior are i>
//    i=13 -> 2k+1 i-> 1 poz
//    13-1 ->12 -> 8k+4 -> 4 poz
//    12-4 -> 8 -> 16k+8 -> pozitii
//    8-8 -> 0
//update la pozitia i ? adun x la pozitia i
//17 bi=1 17+1=18
//18 bi=2 18+2=20
//20 bi=4 20+4=24
//24 bi=8 24+8=32
//32 32 64
//64 64 128
//
//bi(x) = x&(-x)
//
//suma la i
//
//cat timp poz != 0
//aduna val din poz
//scade bit inf din poz
//