#include <bits/stdc++.h>
using namespace std;
#define MAX_N 100005
ifstream fin ("aib.in");
ofstream fout ("aib.out");
int A[MAX_N];
int Tree[MAX_N];
int N, M;
void update (int val, int indx)
{
    while (indx <= N)
    {
        Tree[indx] += val;
        indx = indx + (indx & -indx);
    }
}
int RMQ (int x)
{
    if (x == 0)
        return 0;
    return Tree[x] + RMQ (x - (x & (-x)));
}
int search (int x)
{
    int i = 1;
    while (i <= N)
    {
        if (Tree[i] == x)
            return i;
        if (Tree[i] > x)
        {
            int left = i / 2;
            int right = i;
            while (left < right)
            {
                int mid = (left + right) / 2;
                int val = RMQ (mid);
                if (x <= val)
                    right = mid;
                else
                    left = mid + 1;
            }
            if (RMQ (left) == x)
                return left;
            else
                return -1;
        }
        i *= 2;
    }
    if (i > N && (i / 2 != N))
    {
        i /= 2;
        int left = i + 1;
        int right = N;
        while (left < right)
        {
            int mid = (left + right) / 2;
            int val = RMQ (mid);
            if (x <= val)
            {
                right = mid;
            }
            else
                left = mid + 1;
        }
        if (RMQ (left) == x)
            return left;
        else
            return -1;
    }
}
int main ()
{
    fin >> N >> M;
    for (int i = 1; i <= N; i++)
        fin >> A[i];
    for (int i = 1; i <= N; i++)
        update (A[i], i);
    for (int i = 1; i <= M; i++)
    {
        int p;
        fin >> p;
        if (p == 0)
        {
            int a, b;
            fin >> a >> b;
            update (b, a);
        }
        else if (p == 1)
        {
            int a, b;
            fin >> a >> b;
            fout << RMQ (b) - RMQ (a - 1) << "\n";
        }
        else
        {
            int x;
            fin >> x;
            fout << search (x) << "\n";
        }
    }
}