#include <iostream>
#include <cstdio>
using namespace std;

int aib[100001], n;

int thing(int x)
{
    /// example
    /// x  = b101100100
    /// x-1= b101100011 = y
    /// x^y= b000000111 = z
    /// z&x= b000000100

    return (x ^ (x - 1)) & x;
}

void Add(int pos, int val)
{
    for (int i = pos; i <= n; i += thing(i))
        aib[i] += val;
}

int Query(int pos)
{
    int x = 0;
    for (int i = pos; i > 0; i -= thing(i))
        x += aib[i];
    return x;
}

int Query2(int a, int left = 1, int right = n)
{
    if (left > right) return -1;

    if (left == right)
        return Query(left) == a ? right : -1;

    int mid = (left + right) / 2;
    int q = Query(mid);
    if (q == a) return mid;
    if (q < a)
        return Query2(a, mid + 1, right);
    else
        return Query2(a, left, mid);
}

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

    int m;
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++)
    {
        int a;
        scanf("%d",&a);
        Add(i, a);
    }

    for (int i=1; i<=m; i++)
    {
        int x,a,b=0;
        scanf("%d%d",&x,&a);
        if (x != 2) scanf("%d",&b);

        if(x==0) Add(a,b);
        if(x==1) printf("%d\n", Query(b) - Query(a - 1));
        if(x==2) printf("%d\n", Query2(a));
    }


    return 0;
}