///#include <iostream>
#include <fstream>
#include <stdio.h>

using namespace std;
const int SIZE = 1e5+10;
FILE *infile = fopen("aib.in", "r");

///ifstream cin("aib.in");
ofstream cout("aib.out");

int v[SIZE], n, m, aux;
int cer, a, b;

int getp2(int n)
{
    return n & (n ^ (n-1));
}

void update(int ind, int val)
{
    int p2 = 1;
    while(p2<=n)
    {
        p2 = getp2(ind);
        v[ind] += val, ind += p2;
    }
}

int qry(int ind)
{
    int p2 = 1, sum = 0;
    while(ind)
    {
        p2 = getp2(ind);
        sum += v[ind], ind -= p2;
    }
    return sum;
}

int bins(int sum)
{
    int st=1, dr=n, mid, rez;
    while(st<=dr)
    {
        mid = (st+dr)>>1;
        rez = qry(mid);
        if(rez==sum) return mid;
        if(rez>sum) dr = mid-1;
        else st = mid+1;
    }
    return -1;
}

int main()
{
    fscanf(infile, "%d %d", &n, &m);
    for(int i=1; i<=n; i++)
        fscanf(infile, "%d", &aux), update(i, aux);
    while(m--)
    {
        fscanf(infile, "%d %d", &cer, &a);
        if(cer<2) fscanf(infile, "%d", &b);
        if(!cer) update(a, b);
        else if(cer<2) cout<<qry(b)-qry(a-1)<<'\n';
        else cout<<bins(a)<<'\n';
    }
    return 0;
}