#include <iostream>
#include <fstream>
#define zeros(x) ((x^(x-1))&x)

using namespace std;

ifstream in("aib.in");
ofstream out("aib.out");
const int NMAX = 100001;
int AIB[NMAX];
int SUM[NMAX];
int n,m;

void Add(int,int);
void citire()
{
    in>>n>>m;
    int x;
    for(int i=1;i<=n;i++)
    {
        in>>x;
        Add(i,x);
    }
}

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

int Sum(int x)
{
    int sum = 0;
    for(int i=x;i>0;i-=zeros(i))
        sum+=AIB[i];
    return sum;
}

void sum_partial()
{
    for(int i=1;i<=n;i++)
        SUM[i] = Sum(i);
}

int binar(int a)
{
    int x = 1,y=n;
    int m;
    while(x<=y)
    {
        m = (x+y)/2;
        if(SUM[m]==a && SUM[m-1] < a)
            return m;
        else
        {
            if(SUM[m] >= a)
                y = m-1;
            else
                x = m+1;
        }
    }
    return -1;
}

int main()
{
    citire();
    int q,a,b;
    for(int i=1;i<=m;i++)
    {
        in>>q;
        if(q==0)
        {
            in>>a>>b;
            Add(a,b);
            continue;
        }
        if(q==1)
        {
            in>>a>>b;
            out<<Sum(b)-Sum(a-1)<<"\n";
            continue;
        }
        if(q==2)
        {
            in>>a;
            sum_partial();
            out<<binar(a)<<"\n";
            continue;
        }
    }
    in.close();
    out.close();
    return 0;
}