#include <fstream>
#define zeros(x) (x ^ (x-1)) & x
using namespace std;
ifstream cin("aib.in");
ofstream cout("aib.out");
int aib[100005],days,number_query,type,a,b,i,x;
void Update(int x,int quantity){
    int i;

    for(i = x;i <= days;i+=zeros(i)){
        aib[i] += quantity;
    }
}
int sum(int x){
    int i,sol = 0;
    for(i = x;i > 0;i -= zeros(i)){
        sol += aib[i];
    }
    return sol;
}
int main()
{
    cin >> days >> number_query;
    for(i = 1;i <= days;i++){
        cin >> x;
        Update(i,x);
    }
    for(i = 1;i <= number_query;i++){
        cin >> type;
        cin >> a;
        if(type!=2)
            cin >> b;
        if(type == 0){
            Update(a,b);
        }
        if(type == 1){
            cout << sum(b) - sum(a-1) << "\n";
        }
        if(type == 2){
            int r = 0,pas = 1 << 16;
            while(pas){
                if(r+pas <= days && sum(r+pas) < a){
                    r+=pas;
                }
                pas /= 2;
            }
            r++;
            if(r <= days && sum(r) == a)
                cout << r << "\n";
            else
                cout << "-1\n";
        }
    }
    return 0;
}