#include <iostream>
#include <fstream>
#define nmax 100005

using namespace std;

int n, m, x, tip, val, pos, a, b;
int AIB[nmax];

void update(int val, int pos)
{
    while (pos <= n)
    {
        AIB[pos] += val;
        pos += (pos^(pos-1))&pos;
    }
}

int query(int pos)
{
    int s = 0;
    while (pos > 0)
    {
        s += AIB[pos];
        pos -= (pos^(pos-1))&pos;
    }
    return s;
}

int bs(int lo, int hi, int val)
{
    int mid;
    while (lo <= hi)
    {
        mid = (lo + hi) >> 1;
        if (val == AIB[mid])
            return mid;
        if (val > AIB[mid])
            lo = mid + 1;
        else
            hi = mid - 1;
    }
    return -1;
}

int main()
{
    
    ifstream fi("aib.in");
    ofstream fo("aib.out");
    
    fi >> n >> m;
    
    for (int i = 1; i <= n; i++)
    {
        fi >> x;
        update(x, i);
    }
    
    for (int i = 1; i <= m; i++)
    {
        fi >> tip;
        switch(tip)
        {
            case 0:
                // update
                fi >> pos >> val;
                update(val, pos);
                break;
            case 1:
                //query
                fi >> a >> b;
                fo << query(b) - query(a-1) << "\n";
                break;
            case 2:
                //caut bin
                fi >> a;
                fo << bs(1, n, a) << "\n";
                break;
        }
    }
    
    fi.close();
    fo.close();
    
    return 0;
}