#include <bits/stdc++.h>

using namespace std;

inline int bub(int a)  {
    return a & (-a);
}

const int maxn = 1e5 + 5;

int n, m;
int aib[maxn];
int v[maxn];

inline void add(int a, int b)  {
    while(a <= n)  {
        aib[a] += b;
        a += bub(a);
    }
}

inline int sum(int poz)  {
    int sum = 0;
    while(poz)  {
        sum += aib[poz];
        poz -= bub(poz);
    }
    return sum;
}

int main()  {
    ifstream fin("aib.in");
    ofstream fout("aib.out");
    fin >> n >> m;
    for(int i = 1;i <= n;i++)  {
        fin >> v[i];
        add(i, v[i]);
    }
    for(int i = 1;i <= m;i++)  {
        int a, b, c;
        fin >> a >> b;
        if(a == 0 || a == 1)
            fin >> c;
        if(a == 0)  {
            add(b, c);
        }
        else if(a == 1)  {
            fout << sum(c) - sum(b - 1) << "\n";
        }
        else if(a == 2)  {
            int r = 0, pas = 1 << 17;
            while(pas)  {
                if(r + pas <= n && sum(r + pas) < b)
                    r += pas;
                pas >>= 1;
            }
            r++;
            if(sum(r) != b)
                fout << "-1\n";
            else
                fout << r << "\n";
        }
    }
    return 0;
}