#include <bits/stdc++.h>

using namespace std;

const int MAXN = 300005;
int N, M, Q;
int A[MAXN];
int fav_id[MAXN]; 
set<int> pos[MAXN]; 
multiset<int> head_gaps; 
int tree[4 * MAXN];

void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        tree[node] = val;
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid) update(2 * node, start, mid, idx, val);
    else update(2 * node + 1, mid + 1, end, idx, val);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    return max(query(2 * node, start, mid, l, r), query(2 * node + 1, mid + 1, end, l, r));
}

void add_gap(int a, int b) {
    if (a > b) return;
    if (a == 1) {
        head_gaps.insert(b);
        update(1, 1, N + 1, 1, *head_gaps.rbegin());
    } else {
        update(1, 1, N + 1, a, b);
    }
}

void remove_gap(int a, int b) {
    if (a > b) return;
    if (a == 1) {
        auto it = head_gaps.find(b);
        if (it != head_gaps.end()) head_gaps.erase(it);
        update(1, 1, N + 1, 1, head_gaps.empty() ? 0 : *head_gaps.rbegin());
    } else {
        update(1, 1, N + 1, a, 0);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M >> Q;
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= M; i++) {
        int b;
        cin >> b;
        fav_id[b] = i;
        pos[i].insert(0);
        pos[i].insert(N + 1);
    }

    for (int i = 1; i <= N; i++) {
        if (fav_id[A[i]]) {
            pos[fav_id[A[i]]].insert(i);
        }
    }

    for (int i = 1; i <= M; i++) {
        for (auto it = pos[i].begin(); next(it) != pos[i].end(); ++it) {
            add_gap(*it + 1, *next(it) - 1);
        }
    }

    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int k, x;
            cin >> k >> x;
            if (A[k] == x) continue;

            if (fav_id[A[k]]) {
                int id = fav_id[A[k]];
                auto it = pos[id].find(k);
                int pr = *prev(it), nx = *next(it);
                remove_gap(pr + 1, k - 1);
                remove_gap(k + 1, nx - 1);
                pos[id].erase(it);
                add_gap(pr + 1, nx - 1);
            }

            A[k] = x;

            if (fav_id[A[k]]) {
                int id = fav_id[A[k]];
                auto it = pos[id].insert(k).first;
                int pr = *prev(it), nx = *next(it);
                remove_gap(pr + 1, nx - 1);
                add_gap(pr + 1, k - 1);
                add_gap(k + 1, nx - 1);
            }
        } else {
            int l, r; cin >> l >> r;
            if (query(1, 1, N + 1, 1, l) >= r) cout << "NEM\n";
            else cout << "IGEN\n";
        }
    }

    return 0;
}