#include <fstream>
#define nmax 100005

using namespace std;

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

int v[nmax], aib[nmax];

int n, m, query, a, b, suma, sumb;

int lsd(int x)
{
    return ((x^(x-1))&x);
}

void update(int x, int c)
{
    for(int i=x; i<=n; i+=lsd(i))
    {
        aib[i] += c;
    }
}

int sum(int x)
{
    int ans = 0;
    for(int i=x; i>=1; i-=lsd(i))
    {
        ans += aib[i];
    }
    return ans;
}

int bs(int st, int dr, int x)
{
    int med;
    while(st<=dr)
    {
        med = (st+dr)/2;
        int aux = sum(med);
        if(aux == a)
            return med;
        if(aux < a)
        {
            st = med + 1;
        }
        else
            dr = med - 1;
    }
    return -1;
}

int main()
{
    in>>n>>m;
    for(int i=1; i<=n; i++)
    {
        in>>v[i];
        update(i, v[i]);
    }
    for(int i=1; i<=m; i++)
    {
        in>>query;
        if(query == 0)
        {
            in>>a>>b;
            update(a,b);
        }
        if(query == 1)
        {
            in>>a>>b;
            out<<sum(b)- sum(a-1)<<"\n";
        }
        if(query == 2)
        {
            in>>a;
            out<<bs(1,n,a)<<"\n";
        }
    }
    return 0;
}