#include <fstream>
#include <algorithm>

using namespace std;

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

const int nmax = 100500;
const int mod = 9917;

int n, aib[nmax], sol, a[nmax], m;

int ub(int x)
{
    return (x&(-x));
}

void add(int p, int val)
{
    for(int i = p; i <= n; i += ub(i))
    {
        aib[i] += val;
        aib[i] %= mod;
    }
}

int sum(int p)
{
    int rez = 0;
    for(int i = p; i >= 1; i -= ub(i))
    {
        rez += aib[i];
        rez %= mod;
    }

    return rez;
}

int found(int x)
{
    for(int i = 1; i <= n; i += ub(i))
        if(sum(i) == x)
            return i;

    return -1;
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        int x;
        f >> x;
        add(i, x);
    }

    for(int i = 1; i <= m; i ++)
    {
        int tip;
        f >> tip;
        if(tip == 0)
        {
            int a, x;
            f >> a >> x;
            add(a, x);
        }

        else if(tip == 1)
        {
            int a, b;
            f >> a >> b;
            g << sum(b) - sum(a - 1) << '\n';
        }

        else
        {
            int x;
            f >> x;
            g << found(x) << '\n';
        }
    }

    return 0;
}