#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <climits>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <iomanip>
#include <stack>
#include <cstdio>

using namespace std;

FILE *fin=fopen("aib.in", "r");
FILE *fout=fopen("aib.out", "w");

unsigned const maxb=8192;

#define baza 10
#define MAX 100010
#define MOD 104659

typedef long long int lli;

int x[MAX], n;

int sum(int a)
{
    int s=0;
    while(a)
    {
        s+=x[a];
        a-=(a&(a^(a-1)));
    }
    return s;
}

void zero(int a, int b)
{
    while(a<=n)
    {

        x[a]+=b;
        a+=(a^(a&(a-1)));
    }
}

void unu(int a, int b)
{
    fprintf(fout,"%d\n",sum(b)-sum(a-1));
}

void doi(int a)
{
   // cout<<"ffff";
    int st=0, dr=n+1, m;
    while(st<dr)
    {
        m=(st+dr)/2;
        int l=sum(m);
        if(l==a)
        {
            fprintf(fout, "%d\n", m);
            return;
        }
        else if(l<a)
            st=m+1;
        else
            dr=m-1;
    }
}

int main()
{
    int nr, i, a1, a2, y, ci;
    fscanf(fin,"%d %d", &n, &nr);
    for(i=1;i<=n;i++)
    {
        fscanf(fin, "%d", &a1);
        zero(i,a1);
    }


    for(i=1;i<=nr;i++)
    {
        fscanf(fin, "%d", &a1);
        if(a1==0)
        {
            fscanf(fin, "%d %d", &a1, &a2);
            zero(a1, a2);
        }
        else if(a1==1)
        {
            fscanf(fin,"%d %d",&a1, &a2);
            unu(a1, a2);
        }
        else
        {
            fscanf(fin, "%d", &a2);
            doi(a2);
        }
    }




    return 0;
}