#include <iostream>
#include <fstream>
#define DEBUG 0

using namespace std;

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

int aib[100100], n;

void update(int val, int poz)
{
    for(int i = poz; i <= n; i += i&(-i))
        aib[i] += val;
}

int query(int poz)
{
    int s = 0;

    for(int i = poz; i; i -= i&(-i))
        s += aib[i];

    return s;
}

int binarySearch(int sum)
{
    int l = 1, r = n, x = n, rez = -1;

    if(query(n) == sum)
        rez = n;

    while(l <= r)
    {
        x = (l+r) >> 1;
        int aux = query(x);

        if(aux == sum)
        {
            rez = x;
            r = x-1;
        }
        else
        {
            if(aux > sum)
                r = x-1;
            else
                l = x+1;

            if(DEBUG)
                cout << "l:" << l << "  r:" << r << '\n' << '\n';
        }
    }

    return rez;
}

int main()
{
    int m;
    in >> n >> m;

    for(int i = 1; i <= n; i++)
    {
        int x;
        in >> x;
        update(x, i);
    }

    if(DEBUG)
    {
        for(int i = 1; i <= n; i++)
            cout << aib[i] << ' ';
        cout << "\n\n\n";

        cout << query(n) << '\n';
        cout << binarySearch(90) << ' ' << binarySearch(25) << '\n';
        cout << binarySearch(229);
    }

    while(m)
    {
        int aux, x, y;
        in >> aux >> x;

        if(aux == 1)
        {
            in >> y;
            out << query(y) - query(x-1) << '\n';
        }
        else
        {
            if(aux == 0)
            {
                in >> y;
                update(y, x);
            }
            else
                out << binarySearch(x) << '\n';
        }
        m--;
    }

    return 0;
}