#include <cstdio>

using namespace std;

const int nmax=100000;
int n;
int aib[nmax+1];

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

void update(int pos, int val)
{
    for(int i=pos;i<=n;i+=lsb(i))
        aib[i]+=val;
}

int querry(int pos)
{
    int ans=0;
    for(int i=pos;i>0;i-=lsb(i))
        ans+=aib[i];
    return ans;
}

int binary(int pos)
{
    int ans=0, sc=0;
    for(int k=1<<15;k>0;k>>=1)
        if(ans+k<=n && sc+aib[ans+k]<=pos)
        {
            ans+=k;
            sc+=aib[ans];
        }
    if(sc!=pos || ans==0)
        return -1;
    return ans;
}
int main()
{
	freopen("aib.in", "r", stdin);
	freopen("aib.out", "w", stdout);
    int m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d", &x);
		update(i, x);
	}
	int x, y;
    for(int i=0;i<m;i++)
	{
		int t;
		scanf("%d", &t);
		if(t==0)
		{
			scanf("%d%d", &x, &y);
			update(x, y);
		}
		else if(t==1)
		{
			scanf("%d%d", &x, &y);
			printf("%d\n", querry(y) - querry(x-1));
		}
		else if(t==2)
		{
			scanf("%d", &x);
			printf("%d\n", binary(x));
		}
	}
    return 0;
}