#include <cstdio>

#define sum(x) (x & (-x))

using namespace std;

int v[100010];
int n, m;

void add (int x, int poz)
{
    for (int i = poz; i <= n; i += sum(i))
        v[i] += x;
}

int suma (int poz)
{
    int rez = 0;
    for (int i = poz; i; i -= sum(i))
        rez += v[i];

    return rez;
}

int cautbin (int x)
{
    int a = 1, b = n;
    while (a <= b)
    {
        int m = (a + b) / 2;
        if (x == suma (m)) return m;
        else if (x > suma (m)) a = m + 1;
        else b = m - 1;
    }

    return -1;
}

int main ()
{
    freopen ("aib.in", "r", stdin);
    freopen ("aib.out", "w", stdout);

    scanf ("%d %d", &n, &m);

    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf ("%d", &x);

        add (x, i);
    }

    for (int i = 1; i <= m; i++)
    {
        int x, a, b;
        scanf ("%d", &x);

        if (!x)
        {
            scanf ("%d %d", &a, &b);
            add (b, a);
        }

        else if (x == 1)
        {
            scanf ("%d %d", &a, &b);
            printf ("%d\n", suma (b) - suma (a - 1));
        }

        else
        {
            scanf ("%d", &a);
            printf ("%d\n", cautbin (a));
        }
    }

    return 0;
}