#include <bits/stdc++.h>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int v[100001];
int aib[100001];
int n;
void update(int node,int val)
{
    for(;node<=n;node+=(node & (-node)))
    {
        aib[node]+=val;
    }
}
int query(int node)
{
    int ans=0;
    for(;node;node-=(node & (-node)))
    {
        ans+=aib[node];
    }
    return ans;
}
int main()
{
    int m,t,a,b;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fin>>v[i];
        update(i,v[i]);
    }
    for(int i=1;i<=m;i++)
    {
        fin>>t;
        if(t==0)
        {
            fin>>a>>b;
            update(a,b);
        }
        else if(t==1)
        {
            fin>>a>>b;
            if(a==1)
            {
                fout<<query(b);
                continue;
            }
            fout<<query(b)-query(a-1)<<'\n';
        }
        else
        {
            fin>>a;
            int st=1,dr=n,ans;
            while(st<=dr)
            {
                int mid=(st+dr)/2;
                int x=query(mid);
                if(x>=a)
                {
                    if(x==a) ans=mid;
                    dr=mid-1;
                }
                else
                {
                    st=mid+1;
                }
            }
            fout<<ans<<'\n';
        }
    }
    return 0;
}