#include <cstdio>
using namespace std;
#define zeros(x) ((x ^ (x - 1)) & x)
int aib[100010] , n , i , m , x , a , b , ans , type;
void Update (int x , int i)
{
    for (int j = i ; j <= n ; j += zeros(j))
        aib[j] += x;
}

int Sum (int x)
{
    int S = 0;
    for (int i = x ; i > 0 ; i -= zeros(i))
        S += aib[i];
    return S;
}

int P (int x)
{
    int l = 1 , r = n , mid;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (x == Sum(mid))
            return mid;
        else
            if (x > Sum(mid))
                l = mid + 1;
        else
            r = mid - 1;
    }
    return -1;
}

int main ()
{
    freopen ("aib.in" , "r" , stdin);
    freopen ("aib.out" , "w" , stdout);

    scanf ("%d %d" , &n , &m);
    for (i = 1 ; i <= n ; ++i)
        scanf ("%d" , &x) , Update(x , i);
    for (i = 1 ; i <= m ; ++i)
    {
        scanf ("%d" , &type);
        if (type == 0)
            scanf ("%d %d" , &a , &b) , Update(b , a);
        else
            if (type == 1)
                scanf ("%d %d" , &a , &b) , printf ("%d\n" , Sum(b) - Sum(a-1));
            else
                if (type == 2)
                    scanf ("%d" , &ans) , printf ("%d\n" , P(ans));
    }
    return 0;
}