#include <fstream>

using namespace std;

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

int n , q , v[100005];

void update(int poz , int val)
{
    for ( int i = poz ; i <= n ; i +=(i&-i))
        v[i] += 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++)
    {
        int x = 0;
        f >> x ;
        update(i , x);
    }

    for ( int i = 1 ; i <= q ; i++)
    {
        int cerinta = 0 , x = 0 , y = 0;

        f >> cerinta;
        if(cerinta == 0)
        {
            f >> x >> y;
            update(x , y);
        }
        if(cerinta == 1)
        {
            f >> x >> y;
            g << querry(y) - querry(x - 1) << '\n';
        }
        if(cerinta == 2)
        {
            f >> x;
            int left = 1 , right = n , poz = -1;
            while(left <= right)
            {
                int mid = (left + right) / 2;

                if(querry(mid) == x)
                {
                    poz = mid;
                    left = right + 1;
                }
                else
                    if(querry(mid) < x)
                    {
                        left = mid + 1;
                    }
                else
                    {
                        right = mid - 1;
                    }
            }
            g << poz << '\n';
        }
    }
}