#include <bits/stdc++.h>
#define NUM 100005
#define zeros(x) (x&(-x))
using namespace std;
int AIB[NUM];
int n, m;
ifstream fin ("aib.in");
ofstream fout ("aib.out");

void Add(int x, int quantity)
{
    for(int i = x; i <= n; i+=zeros(i))
        AIB[i] += quantity;
}

int Compute(int x)
{
    int ret = 0;
    for(int i = x; i >= 1; i -=zeros(i))
        ret += AIB[i];
    return ret;
}
void Read()
{
    int op, a, b;
    fin >> n >> m;
    for(int i = 1; i <= n; i++)
        {
            fin >> a;
            Add(i, a);
        }
    for(int i = 1; i <= m; i++)
    {
        fin >> op;
        if(op == 0)
        {
            fin >> a >> b;
            Add(a, b);

        }
        else if(op == 1)
        {
            fin >> a >> b;
            fout << Compute(b) - Compute(a - 1) << "\n";
        }
        else if(op == 2)
        {
            fin >> a;
            int poz = -1;
            int st, dr, mij;
            st = 1;
            dr = n;
            while(st <= dr && poz == -1)
            {
                mij = (st + dr) / 2;
                if(Compute(mij) == a) poz = mij;
                else if(Compute(mij) > a) dr = mij - 1;
                else st = mij + 1;
            }
            fout << poz << "\n";
        }
    }
}

int main()
{
    Read();
    return 0;
}