#include <iostream>
#include <deque>
#include <vector>
#include <cstring>
#include <bitset>
#include <algorithm>
#define INF 1000010
#define uint unsigned int
#define ll long long
#define step(x) (x&(-x))
using namespace std;

uint N, M, x, i, AIB[100010], t, a, b, st, dr, mid, v;

void update(uint val, uint pos)
{
    for(; pos <= N; pos += step(pos))
        AIB[pos] = AIB[pos] + val;
}

uint query(int pos)
{
    uint res = 0;
    for( ; pos; pos -= step(pos))
    {
        res = res + AIB[pos];
    }
    return res;
}


int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d%d", &N, &M);
    for(i = 1; i <= N; i++)
    {
        scanf("%d", &x);
        update(x, i);
    }
    for(;M;--M)
    {
        scanf("%d", &t);
        if(t == 0)
        {
            scanf("%d%d", &a, &b);
            update(b, a);
        }
        if(t == 1)
        {
            scanf("%d%d", &a, &b);
            printf("%d\n", query(b) - query(a-1));
        }
        if(t == 2)
        {
            scanf("%d", &a);
            st = 1;
            dr = N;
            x =  -1;
            while(st <= dr)
            {
                mid = (st + dr) / 2;
                v = query(mid);
                if(v == a)
                    x = mid;
                if(v > a)
                    dr = mid - 1;
                else
                    st = mid + 1;
            }
            printf("%d\n", x);
        }
    }
}