#include <bits/stdc++.h>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n,m,x,type;
vector<int>aib;
void update(int node,int value)
{
    for(; node<=n; node+=node&(-node))
        aib[node]+=value;
}
int query(int node)
{
    int ans=0;
    for(; node>0; node-=node&(-node))
        ans+=aib[node];
    return ans;
}
int BinarySearch(int value)
{
    int left=1,right=n;
    while(left<=right)
    {
        int middle=(left+right)/2;
        int q=query(middle);
        if(q==value)
            return middle;
        if(q<value)
            left=middle+1;
        else
            right=middle-1;
    }
    return -1;
}
int main()
{
    f>>n>>m;
    aib=vector<int>(n+5,0);
    for(int i=1; i<=n; i++)
    {
        f>>x;
        update(i,x);
    }
    for(int i=1; i<=m; i++)
    {
        f>>type;
        if(type==0)
        {
            int pos,value;
            f>>pos>>value;
            update(pos,value);
        }
        else if(type==1)
        {
            int left,right;
            f>>left>>right;
            g<<query(right)-query(left-1)<<"\n";
        }
        else
        {
            int value;
            f>>value;
            g<<BinarySearch(value)<<"\n";
        }
    }
    return 0;
}