#include<fstream>
using namespace std;

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

int AIB[100010],N,Q,s;

void update(int x,int val)
{
    for (;x <= N;x += (x & (-x)))
        AIB[x] += val;
}

int query(int x)
{
    s = 0;
    for (;x;x-= (x & (-x)))
        s+=AIB[x];
    return s;
}

int main()
{
    in >> N >> Q;
    for (int i = 1;i <= N;++i)
    {
        int x;
        in >> x;
        update(i,x);
    }
    for (int i = 1;i <= Q;++i)
    {
        int op,a,b;
        in >> op;
        switch (op)
        {
            case 0:
                in >> a >> b;
                update(a, b);
                break;
            case 1:
                in >> a >> b;
                out << query(b) - query(a - 1) << '\n';
                break;

            case 2:
                in >> a;
                int l = 1, r = N,mid;
                int pos = -1;
                while (l <= r)
                {
                    mid = (l + r) >> 1;
                    if (query(mid) == a)
                    {
                        pos = mid;
                        r = mid - 1;
                    }
                    else if (query(mid) > a)
                        r = mid - 1;
                    else
                        l = mid + 1;
                }
                out << pos<<'\n';
                break;
        }
    }
    return 0;
}