#include <fstream>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int v[100010], a[100011];
int n, m;
void update(int poz, int val)
{
for(int i=poz;i<=n;i+=(i&-i))
{
a[i]+=val;
}
}
int query(int poz)
{
int s=0;
for(int i=poz;i>0;i-=(i&-i))
{
s+=a[i];
}
return s;
}
int cautbin(int k)
{
int st=1, dr=n;
while(st<=dr)
{
int mid=(st+dr)/2;
int crt=query(mid);
if(crt>k)
{
dr=mid-1;
}
else
if(crt==k)
{
return mid;
}
else
{
st=mid+1;
}
}
return -1;
}
int main()
{
int i, t, poz, val, a, b, k;
fin>>n>>m;
for(i=1;i<=n;i++)
{
fin>>v[i];
update(i, v[i]);
}
for(i=1;i<=m;i++)
{
fin>>t;
if(t==0)
{
fin>>poz>>val;
update(poz, val);
}
else
if(t==1)
{
fin>>a>>b;
fout<<query(b)-query(a-1)<<"\n";
}
else
{
fin>>k;
fout<<cautbin(k)<<"\n";
}
}
}