#include <cstdio>
#define nmax 100000+5
using namespace std;

int N, M;
int v[nmax];

int z(int x)
{
    return x & ~(x-1);
}

void adunare(int a, int b)
{
    while (a <= N)
    {
        v[a] += b;
        a += z(a);
    }
}

int suma1(int a)
{
    int s = 0;
    while (a > 0)
    {
        s += v[a];
        a -= z(a);
    }
    return s;
}

int suma2(int a, int b)
{
    return suma1(b) - suma1(a-1);
}

int cautare(int s)
{
    int i, x;
    for (i = 1; (x = suma1(i)) <= s; i++)
        if (x == s)
            return i;
    return -1;
}

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

    int i, j;
    int c;
    int a, b;

    scanf("%d%d", &N, &M);
    for (i = 1; i <= N; i++)
    {
        scanf("%d", &c);
        adunare(i, c);
    }
    for (j = 1; j <= M; j++)
    {
        scanf("%d", &c);
        if (c == 0)
        {
            scanf("%d%d", &a, &b);
            adunare(a, b);
        }
        else if (c == 1)
        {
            scanf("%d%d", &a, &b);
            printf("%d\n", suma2(a, b));
        }
        else if (c == 2)
        {
            scanf("%d", &a);
            printf("%d\n", cautare(a));
        }
    }

    return 0;
}