#include <iostream>
#include <fstream>
using namespace std;

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

int n,m;
int aib[100005];

int query(int p)
{
    int s = 0;
    for(int i = p; i >= 1; i -= i&(-i))
        s += aib[i];

    return s;
}

int update(int p, int x)
{
    for(int i = p; i <= n; i += i&(-i))
        aib[i] += x;
}

int caut_bin(int x)
{
    int lo = 1,hi = n;
    while(lo <= hi)
    {
        int mid = (lo+hi)/2;
        int s = query(mid);
        if (s == x) return mid;
        if (s < x) lo = mid + 1;
        if (s > x) hi = mid - 1;
    }

    return -1;
}

int main()
{

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

    for(int i = 1; i<=m; i++)
    {
        int type;
        f >> type;

        if (type == 0)
            {
                int x,y;
                f >> x >> y;
                update(x,y);
            }
        if (type == 1)
        {
            int x,y;
            f >> x >> y;
            g << query(y) - query(x-1)<<'\n';
        }
        if (type == 2)
        {
            int x;
            f >> x;
            g << caut_bin(x)<<'\n';
        }
    }

    return 0;
}