#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int get(int i, vector<int>&t)
{
    int sum=0;
    for(;i>0; i-=i&(-i))
    {
        sum+=t[i];
    }
    return sum;
}
void update(int i, int x, int n, vector<int> &t)
{
    for(; i<=n; i+=i&(-i))
    {
        t[i]+=x;
    }
}
int main()
{
    int nr, a, b;
    int M, n;
    fin>>n>>M;
    vector<int>A(n+1);
    vector<int>t(n+1, 0);
    for(int i=1; i<=n; i++)
    {
        fin>>A[i];
    }
    for(int i=1; i<=n; i++)
    {
        update(i, A[i], n, t);
    }
    for(int i=1; i<=M; i++)
    {
        fin>>nr>>a;
        if(nr==0)
        {
            fin>>b;
            update(a, b, n, t);
        }
        if(nr==1)
            {
                fin>>b;
                fout<<get(b, t)-get(a-1, t)<<'\n';
            }
        if(nr==2)
        {
            int st=0, dr=n, mij;
            mij=(st+dr)/2;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                if(get(mij, t)==a)
                {
                    fout<<mij<<'\n';
                    break;
                }
                else if(get(mij, t)<a)
                    st=mij+1;
                else dr=mij-1;
            }
        }
    }
    return 0;
}