2006 C

#include <bits/stdc++.h>
// tiom4eg's precompiler options
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
// Flags
#define MAXMIN
#define ENDL
//#define AVX2
//#define PBDS
// IO settings
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0)
// Quick types
#define ll long long
#define ld double
#define ull unsigned long long
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define mi vector <vector <int> >
// Quick functions
#ifdef ENDL
#define endl "\n"
#endif
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define pb push_back
#define mp make_pair
#ifdef MAXMIN
#define min(a, b) ((a < b) ? (a) : (b))
#define max(a, b) ((a > b) ? (a) : (b))
#endif
// Quick fors
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
#define EACH(e, a) for (auto& e : a)
// Pragmas
#pragma GCC optimize("O3,unroll-loops") // let the chaos begin!
#ifdef AVX2
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt,tune=native")
#endif
//#pragma GCC comment(linker, "/stack:200000000")
// PBDS
#ifdef PBDS
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update>
#define ook order_of_key
#define fbo find_by_order
using namespace __gnu_pbds;
#endif
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
using namespace std;
mt19937 rng(std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
//#define int long long

/// BEGIN BOILERPLATE CODE

/** Interface */

inline int readChar();
template <class T = int> inline T readInt();
template <class T> inline void writeInt( T x, char end = 0 );
inline void writeChar( int x );
inline void writeWord( const char *s );

/** Read */

static const int buf_size = 4096;

inline int getChar() {
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if (pos == len)
        pos = 0, len = fread(buf, 1, buf_size, stdin);
    if (pos == len)
        return -1;
    return buf[pos++];
}

inline int readChar() {
    int c = getChar();
    while (c <= 32)
        c = getChar();
    return c;
}

template <class T>
inline T readInt() {
    int s = 1, c = readChar();
    T x = 0;
    if (c == '-')
        s = -1, c = getChar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
}

/** Write */

static int write_pos = 0;
static char write_buf[buf_size];

inline void writeChar( int x ) {
    if (write_pos == buf_size)
        fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}

template <class T>
inline void writeInt( T x, char end ) {
    if (x < 0)
        writeChar('-'), x = -x;

    char s[24];
    int n = 0;
    while (x || !n)
        s[n++] = '0' + x % 10, x /= 10;
    while (n--)
        writeChar(s[n]);
    if (end)
        writeChar(end);
}

inline void writeWord( const char *s ) {
    while (*s)
        writeChar(*s++);
}

struct Flusher {
    ~Flusher() {
        if (write_pos)
            fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
    }
} flusher;

/// END BOILERPLATE CODE

const int INF = 1e9, MAX = 5009, M = 1e9 + 9, R = 1 << 19;

struct segtree { // -1 on segment, nearest > 1 on segment
    struct node { int s, d; };
    vector <node> t;
    void merge(int v) { t[v].s = max(t[2 * v].s, t[2 * v + 1].s); }
    void tag(int v, int x, int l) { t[v].s = max(1, t[v].s - x), t[v].d += x; }
    void push(int v, int l) {
        if (!t[v].d) return;
        tag(2 * v, t[v].d, l / 2), tag(2 * v + 1, t[v].d, l / 2);
        t[v].d = 0;
    }
    void build(vi& a) {
        t.assign(2 * R, {1, 0});
        FOR(i, 0, sz(a)) t[R + i].s = a[i];
        RFOR(i, R - 1, 1) merge(i);
    }
    void upd(int ql, int qr, int v = 1, int nl = 0, int nr = R) {
        if (qr <= nl || nr <= ql) return;
        if (ql <= nl && nr <= qr) {
            tag(v, 1, nr - nl);
            return;
        }
        push(v, nr - nl);
        int nm = (nl + nr) / 2;
        upd(ql, qr, v * 2, nl, nm), upd(ql, qr, v * 2 + 1, nm, nr);
        merge(v);
    }
    pii get(int ql, int v = 1, int nl = 0, int nr = R) {
        if (ql >= nr || t[v].s == 1) return {-1, -1};
        if (nl + 1 == nr && t[R + nl].s > 1) return {nl, t[R + nl].s};
        push(v, nr - nl);
        int nm = (nl + nr) / 2;
        pii lres = get(ql, 2 * v, nl, nm);
        if (lres.F >= 0) return lres;
        else return get(ql, 2 * v + 1, nm, nr);
    }
} t;

signed main() {
    fastIO;
    int n, q; n = readInt(), q = readInt();
    vi a(n); FOR(i, 0, n) a[i] = readInt();
    t.build(a);
    FOR(i, 0, q) {
        int tp, l, r; tp = readInt(), l = readInt() - 1, r = readInt();
        if (tp == 1) t.upd(l, r);
        else {
            int x; x = readInt();
            int p = l - 1;
            while (x) {
                pii rq = t.get(p + 1);
                if (rq.F == -1 || rq.F >= r) break;
                p = rq.F, x /= rq.S;
            }
            if (x) writeInt(-1, '\n');
            else writeInt(p + 1, '\n');
        }
    }
}