#include<fstream>
#include<vector>
using namespace std;

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

class AIB
{
    private: int n; vector<int> aib;
    inline int lsb(int x){return x & -x;}

    public: AIB(int _n){n = _n; aib.resize(n + 1,0);}
    int suma(int p)
    {
        int ans = 0; for(int i = p ; i ; i -= lsb(i)) ans += aib[i];
        return ans;
    }

    void update(int p,int v){for(int i = p ; i <= n ; i += lsb(i)) aib[i] += v;}
    int kth(int suma)
    {
        int ans = 0,pas = 1; while(pas < n) pas <<= 1;
        for(; pas ; pas >>= 1)
            {
                if(ans + pas <= n && suma >= aib[ans + pas])
                    ans += pas,suma -= aib[ans];
            }

        if(suma == 0) return ans;
        else return -1;
    }
};


int main()
{
    int n,m,a,b,t; cin >> n >> m; AIB aib(n);
    for(int i = 1; i <= n ; i++)
        {
            cin >> a;
            aib.update(i,a);
        }

    while(m--)
        {
            cin >> t;
            if(t == 1)
                {
                    cin >> a >> b;
                    cout << aib.suma(b) - aib.suma(a - 1) << '\n';
                }

            else if(t == 0)
                {
                    cin >> a >> b;
                    aib.update(a,b);
                }

            else
                {
                    cin >> a;
                    cout << aib.kth(a) << '\n';
                }
        }
}