#include<stdio.h>
#define N_MAX 102400
int arb[2*N_MAX];
int n, m, n2;
int interogare2(int val, int st, int dr, int poz)
{
if (arb[poz] < val)
return -1;
if (st==dr)
{
if (arb[poz] == val)
return st;
else
return -1;
}
if (arb[poz*2] >= val)
return interogare2(val, st, (st+dr)/2, poz*2);
else
return interogare2(val-arb[poz*2], (st+dr)/2 +1, dr, poz*2+1);
}
int interogare(int a, int b, int st, int dr, int poz)
{
if ((a<= st) && (dr <= b))
return arb[poz];
if ((b < st) || (a > dr))
return 0;
return interogare(a, b, st, (st+dr)/2, poz*2) + interogare(a, b, (st+dr)/2+1, dr, poz*2+1);
}
void adauga(int unde, int val)
{
arb[unde]+=val;
if (unde > 1)
adauga(unde/2, val);
}
inline int pozitie(int unde)
{
return n2+unde-1;
}
int main()
{
freopen("aib.in", "r", stdin);
freopen("aib.out", "w", stdout);
int i, a, b, tip;
scanf("%d %d", &n, &m);
n2=1;
while (n2 < n)
{
n2 = n2 << 1;
}
for (i=1; i<=n; i++)
{
scanf("%d", &a);
adauga(pozitie(i), a);
}
for (i=1; i<=m; i++)
{
scanf("%d", &tip);
switch (tip)
{
case 0:
scanf("%d %d", &a, &b);
adauga(pozitie(a), b);
break;
case 1:
scanf("%d %d", &a, &b);
printf("%d\n", interogare(a, b, 1, n2, 1));
break;
case 2:
scanf("%d", &a);
printf("%d\n", interogare2(a, 1, n2, 1));
break;
}
}
fclose(stdout);
return 0;
}