#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");

int n,m;
vector<long long> aib;
vector<int> forBin;

long long int findSum(int stop)
{
    long long int sum=0;
    while(stop>0)
    {
        sum+=aib[stop];
        stop-=stop&-stop;
    }
    return sum;
}
long long int calculateSum(int start,int stop)
{
    if(start==1)
        return findSum(stop);
    return findSum(stop)-findSum(start-1);
}
bool comp(int a,int b)
{
    return findSum(a)<findSum(b);
}
int main()
{

    fin>>n>>m;
    aib.resize(n+1);
    forBin.resize(n+1);
    for(int i=1;i<=n;i++)
        forBin[i]=i;
    for(int i=1;i<=n;i++)
    {
        int j=i,nr;
        fin>>nr;
        while(j<=n)
        {
            aib[j]+=nr;
            j+=j & -j;
        }
    }
    int type,a,b;
    for(int i=1;i<=m;i++)
    {
        fin>>type;
        if(type==1)
        {
            fin>>a>>b;
            while(a<=n)
            {
                aib[a]+=b;
                a+=a & -a;
            }
        }
        if(type==2)
        {
            fin>>a>>b;
            fout<<calculateSum(a,b)<<"\n";
        }
        if(type==3)
        {
            fin>>a;
            int ans=*(lower_bound(forBin.begin()+1,forBin.end(),a,comp));
            if(findSum(ans)==a)
                fout<<ans<<"\n";
            else
                fout<<-1<<"\n";
        }

    }
}