#include <iostream>
#include <fstream>
using namespace std;

#define NMAX 100001

int aib[NMAX],n,m,p,x,y;

ifstream in("aib.in");
ofstream out("aib.out");

inline int lsb(int x)
{
    return (x& (-x));
}

void update(int index,int val)
{
    for(;index<=n;index+=lsb(index))
    {
        //cout << index << " ";
        aib[index]+=val;
    }
}

int read(int index)
{
    int sol = 0;
    for(;index>0;index-=lsb(index))
    {
        sol += aib[index];
    }
    return sol;
}

int bin(int x)
{
    int st=1,dr=n,mij,y;
    while(st<=dr)
    {
        mij = (st+dr)/2;
        y = read(mij);
        if(y == x)
        {
            break;
        }
        else if(y<x)
        {
            st = mij+1;
        }
        else
        {
            dr = mij-1;
        }
    }

    if(st>dr) return -1;
    return mij;
}

int main()
{
    in >> n >> m;
    for(int i=1;i<=n;i++)
    {
        in >> x;
       update(i,x);
    }
    for(int i=0;i<m;i++)
    {
        in >> p;
        if(p==0)
        {
            in >> x >> y;
            update(x,y);
        }
       else if(p==1)
        {

            in >> x >> y;
            out << read(y)-read(x-1) << "\n";
        }
        else if(p==2)
        {
            in >> x;
            out << bin(x) << "\n";
        }
    }

    return 0;
}