#include <iostream>
#include <fstream>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");

int AIB[4100], n, m;

void Update(int x, int pos)
{
    for(int i = pos; i <= n; i += i&(-i)) AIB[i] += x;
}

int Suma(int a)
{
    int suma = 0;
    for(int i = a; i > 0; i -= i&(-i)) suma += AIB[i];
    return suma;
}

int main()
{
    f>>n>>m;
    for(int i = 1; i <= n; i++)
    {
        int x;
        f>>x;
        Update(x,i);
    }
    while(m--)
    {
        int opt,a,b;
        f>>opt;
        if(opt == 0)
        {
            f>>a>>b;
            Update(b,a);
        }
        if(opt == 1)
        {
            f>>a>>b;
            g<<Suma(b) - Suma(a-1)<<'\n';
        }
        if(opt == 2)
        {
            f>>a;
            int s = 1, d = n, sw = 0;
            while(s<=d)
            {
                int mid = (s+d)/2;
                int sum = Suma(mid);
                if(sum == a)
                {
                    g<<mid<<'\n';
                    s = d+1;
                    sw = 1;
                }
                if(sum < a) s = mid+1;
                if(sum > a) d = mid-1;
            }
            if(sw == 0) g<<-1<<'\n';
        }
    }
    return 0;
}