#include <bits/stdc++.h>
using namespace std;
const int s_vec = 100001;
using LL = long long;
ifstream fin("aib.in");
ofstream fout("aib.out");

int nr_elem, nr_query;
LL tree[s_vec];

void aib_add(LL poz, LL val)
{
    while (poz <= nr_elem)
    {
        tree[poz] += val;
        poz += (poz & (-poz));
    }

    return;
}

LL aib_sum(LL poz)
{
    LL sum = 0;
    while (poz)
    {
        sum += tree[poz];
        poz -= (poz & (-poz));
    }

    return sum;
}

LL aib_findk(LL val)
{
    LL st = 0, dr = nr_elem + 1;
    while (st + 1 < dr)
    {
        LL mid = (st + dr)/2;
        LL rez = aib_sum(mid);
        if (rez > val)
            dr = mid;
        else
            st = mid;
    }
    if (aib_sum(st) == val)
        return st;
    else
        return -1;
}

int main()
{
    fin >> nr_elem >> nr_query;
    for (int i = 1; i <= nr_elem; i++)
    {
        LL x;
        fin >> x;
        aib_add(i, x);
    }
    for (int i = 1; i <= nr_query; i++)
    {
        LL a, b, tip;
        fin >> tip;
        if (tip == 0)
        {
            fin >> a >> b;
            aib_add(a, b);
        }
        else if (tip == 1)
        {
            fin >> a >> b;
            fout << aib_sum(b) - aib_sum(a - 1) << "\n";
        }
        else
        {
            fin >> a;
            fout << aib_findk(a) << "\n";
        }
    }
    return 0;
}