#include <bits/stdc++.h>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
const int N = 100010;
int n,q,aib[N];
void add(int val,int poz)
{
    for(int i=poz;i<=n;i+=i&(-i))
        aib[i]+=val;
}
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);
}
int main()
{
    f>>n>>q;
    for(int i=1;i<=n;i++)
    {
        int x;
        f>>x;
        add(x,i);
    }
    for(int i=1;i<=q;i++)
    {
        int tip,a,b;
        f>>tip>>a;
        if(tip==0)
        {
            f>>b;
            add(b,a);
        }
        else if(tip==1)
        {
            f>>b;
            g<<suma(a,b)<<'\n';
        }
        else
        {
            int st=0,dr=n;
            while(dr-st>1)
            {
                int mi=(st+dr)/2;
                if(suma(mi)<a)
                    st=mi;
                else
                    dr=mi;
            }
            if(suma(dr)!=a)
                dr=-1;
            g<<dr<<'\n';
        }

    }
    return 0;
}


//i   : 0 1  2  3  4  5  6  7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
//v[i]: 0 2  3  1  4  5  1  2 7 3  6  5  4  2  1  3  6  7  6  5  2  1
//a[i]:  [2]   [1]   [5]   [2] [3]   [5]   [2]   [3]   [7]   [5]   [2] 2k+1
//
//       [  5]       [  6]     [  9]       [   3]      [  13]          4k+2
//
//       [       10]           [       18]             [        20]    8k+4
//
//       [                   25]                                       16k+8
//
//       [                                          55]
//
//
//
//    i&(-i)
//