#include <fstream>
#define adunare(x) (i & -i)
using namespace std;
ifstream cin("aib.in");
ofstream cout("aib.out");
int n;
int aib[100005];
void update(int a, int b)
{
    int i;
    for(i = a; i <= n; i += adunare(i))
        aib[i] += b;
}
int query(int a)
{
    int i, sum = 0;
    for(i = a; i >= 1; i -= adunare(i))
        sum += aib[i];
    return sum;
}
int main()
{
    int q, i, a, j, b, tip;
    cin >> n >> q;
    for(i = 1; i <= n; i++){
        cin >> a;
        update(i, a);
    }
    for(i = 1; i <= q; i++){
        cin >> tip >> a;
        if(tip == 0 or tip == 1){
            cin >> b;
            if(tip == 0)
                update(a, b);
            else
                cout << query(b) - query(a - 1) << "\n";
            continue;
        }
        else{
            int st = 1, dr = n, med, poz;
            while(st <= dr){
                med = (st + dr) / 2;
                int x = query(med);
                if(x > a)
                    dr = med - 1;
                else if(x < a)
                    st = med + 1;
                else{
                    poz = med;
                    dr = med - 1;
                }
            }
            cout << poz << "\n";
        }
    }
    return 0;
}