#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("aib.in");
ofstream g ("aib.out");

int i = 1 , p , n , v[100005] , q , c , x , y , j = 0 , poz , st , dr;

void update (int poz , int val)
{
    for (int j = poz ; j <= n ; j +=(j&-j))
        v[j] += val;
}

int querry (int x)
{
    int suma = 0;
    for (int i = x ; i > 0 ; i -=(i&-i))
        suma = suma + v[i];
        return suma;
}

int main()
{
    f >> n >> q;
    for (int i = 1 ; i <= n ; i++)
        {
            f >> x;
            update (i , x);
        }
    for (int i = 1 ; i <= q ; i++)
    {
        f >> c;
        if (c == 0)
        {
            f >> x >> y;
            update (x , y);
        }
        else
            if (c == 1)
        {
            f >> x >> y;
            g << querry (y) - querry (x - 1) << '\n';
        }
        else
            if (c == 2)
        {
            f >> x;
            st = 1 , dr = n , poz = -1;
            while (st <= dr)
            {
                int mij = (st + dr) / 2;
                if (querry (mij) == x)
                    poz = mij , st = dr + 1;
                else
                    if (querry (mij) < x)
                    st = mij + 1;
                else
                    dr = mij - 1;
            }
            g << poz << '\n';
        }
    }
    return 0;
}