#include <fstream>
using namespace std;
ifstream fi("aib.in");
ofstream fo("aib.out");
int aib[100005], n ,t;

void Update(int poz, int val)
{
    for (int i = poz; i <= n; i += (i & -i))
        aib[i]+=val;
}

int Suma(int poz)
{
    int sum = 0;
    for (int i = poz; i >= 1; i -= (i & -i))
        sum+=aib[i];
    return sum;
}

int Sum(int a, int b)
{
    return Suma(b) - Suma(a-1);
}

int CautBin(int x)
{
    int st, dr, p, mij, s;
    st = 1; dr = n;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        s = Suma(mij);
        if (s == x) return mij;
        if (s < x) st = mij + 1;
        else dr = mij - 1;
    }
    return -1;
}
int main()
{

    fi >> n >> t;
    for (int q,i = 1; i <= n; i++)
        {   fi >> q; Update(i, q); }

    while(t--)
    {
        int op, x, y;
        fi >> op;
        if (op==0)  { fi >> x >> y;  Update(x, y);  }
        if (op==1)  { fi >> x >> y;  fo << Sum(x, y) << '\n';}
        if (op==2) {  fi>>x;  fo<<CautBin(x)<< '\n';  }
    }
    return 0;
}