#include <cstdio>

using namespace std;

int n;
int c[100002];

void add (int ind, int val)
{
    int poz = 0;
    while (ind <= n)
    {
        c[ind] += val;
        while ((ind & 1<<poz) == 0)
            ++poz;
        ind += 1<<poz;
        ++poz;
    }
}

int sum (int ind)
{
   int result = 0;
   int pos = 0;
   while (ind > 0)
   {
       result += c[ind];
       while ((ind & 1<<pos) == 0)
           ++pos;
        ind -= 1<<pos;
        ++pos;
   }
   return result;
}

int main()
{
    FILE *in = fopen("aib.in", "r");
    FILE *out = fopen("aib.out", "w");

    int m;
    fscanf(in, "%d%d", &n, &m);

    for (int x, i = 1; i <= n; ++i)
    {
        fscanf(in, "%d", &x);
        add(i, x);
    }

    int a, b, t;
    for (int i = 1; i <= m; ++i)
    {
        fscanf(in, "%d%d", &t, &a);
        if (t == 0)
        {
            fscanf(in, "%d", &b);
            add(a, b);
        }
        if (t == 1)
        {
            fscanf(in, "%d", &b);
            int result = sum(b) - sum(a-1);
            fprintf(out, "%d\n", result);
        }
        if (t == 2)
        {
            int result = -1;
            int st = 1;
            int dr = n;
            while (st < dr)
            {
                int mid = (st+dr)/2;
                int s = sum(mid);
                if (s == a)
                {
                    result = mid;
                    break;
                }
                else
                {
                    if (s > a)
                        dr = mid-1;
                    else
                        st = mid+1;
                }
            }
            if (sum(st) == a)
                result = st;
            if (result > -1)
            {
                while (sum(result) == a && result >= 1)
                    --result;
                ++result;
            }
            fprintf(out, "%d\n", result);
        }
    }

    return 0;
}