求条（必关）

#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10;
int len, n, lis[N], sz[N], tot, a[N];
vector <int> bl[N];
inline void insert (int pos, int c) {
    int id = 0;
    while (pos > sz[id + 1]) pos -= sz[++id];
    id++;
    bl[lis[id]].push_back (0);
    sz[lis[id]]++;
    for (int i = sz[lis[id]]; i > pos; i--)
        bl[lis[id]][i - 1] = bl[lis[id]][i - 2];
    bl[lis[id]][pos - 1] = c;
    if (sz[id] == 2 * len) {
        for (int i = tot + 1; i > id + 1; i--)
            lis[i] = lis[i - 1];
        lis[id + 1] = ++tot;
        sz[lis[id]] = len, sz[tot] = len;
        for (int i = len; i < 2 * len; i++)
            bl[tot].push_back (bl[lis[id]][i]);
    }
}
inline int query (int pos) {
    int id = 0;
    while (pos > sz[id + 1]) pos -= sz[++id];
    return bl[lis[id + 1]][pos - 1];
}
int main () {
    ios :: sync_with_stdio (0);
    cin.tie (0), cout.tie (0);
    cin >> n;
    len = sqrt (n);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if ((i - 1) % len == 0) {tot++; sz[tot] = len;}
        bl[tot].push_back (a[i]);
        lis[tot] = tot;
    }
    int q = n;
    while (q--) {
        int op, pos, c;
        cin >> op;
        if (op == 0) {
            cin >> pos >> c;
            insert (pos, c);
        }
        else {
            cin >> pos;
            cout << query (pos) << "\n";
        }
/*        for (int i = 1; i <= tot; i++)
            cout << lis[i] << " ";
        cout << "\n";
        for (int i = 1; i <= tot; i++) {
            cout << i << ":\n";
            for (int j = 0; j < sz[i]; j++)
                cout << bl[i][j] << " ";
            cout << "\n";
        }*/
    }
    return 0;
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5, mod = 10007;
int add[N], mul[N], id[N], n, a[N], len;
inline void update_add (int l, int r, int c) {
    int s = id[l], e = id[r];
    if (s == e) {
        for (int i = (s - 1) * len + 1; i <= min (n, s * len); i++)
            a[i] = (a[i] * mul[id[i]] % mod + add[id[i]]) % mod;
        for (int i = l; i <= r; i++)
            a[i] = (a[i] + c) % mod;
        add[s] = 0, mul[s] = 1;
        return;
    }
    for (int i = (s - 1) * len + 1; i <= s * len; i++)
        a[i] = (a[i] * mul[id[i]] % mod + add[id[i]]) % mod;
    for (int i = l; id[i] == s; i++)
        a[i] = (a[i] + c) % mod;
    add[s] = 0, mul[s] = 1;
    for (int i = (e - 1) * len + 1; i <= min (n, e * len); i++)
        a[i] = (a[i] * mul[id[i]] % mod + add[id[i]]) % mod;
    for (int i = r; id[i] == e; i--)
        a[i] = (a[i] + c) % mod;
    add[e] = 0, mul[e] = 1;
    for (int i = s + 1; i < e; i++)
        add[i] = (c + add[i]) % mod;
}
inline void update_mul (int l, int r, int c) {
    int s = id[l], e = id[r];
    if (s == e) {
        for (int i = (s - 1) * len + 1; i <= min (n, s * len); i++)
            a[i] = (a[i] * mul[id[i]] % mod + add[id[i]]) % mod;
        for (int i = l; i <= r; i++)
            a[i] = a[i] * c % mod;
        add[s] = 0, mul[s] = 1;
        return;
    }
    for (int i = (s - 1) * len + 1; i <= s * len; i++)
        a[i] = (a[i] * mul[id[i]] % mod + add[id[i]]) % mod;
    for (int i = l; id[i] == s; i++)
        a[i] = a[i] * c % mod;
    add[s] = 0, mul[s] = 1;
    for (int i = (e - 1) * len + 1; i <= min (n, e * len); i++)
        a[i] = (a[i] * mul[id[i]] % mod + add[id[i]]) % mod;
    for (int i = r; id[i] == e; i--)
        a[i] = a[i] * c % mod;
    add[e] = 0, mul[e] = 1;
    for (int i = s + 1; i < e; i++) {
        add[i] = add[i] * c % mod;
        mul[i] = mul[i] * c % mod;
    }
}
inline int query (int x) {
    return ((a[x] * mul[id[x]] % mod + add[x]) % mod + mod) % mod;
}
signed main () {
    ios :: sync_with_stdio (0);
    cin.tie (0), cout.tie (0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    len = sqrt (n);
    for (int i = 1; i <= n; i++) {
        id[i] = (i - 1) / len + 1;
        mul[id[i]] = 1;
    }
    int q = n;
    while (q--) {
        int op, l, r, c;
        cin >> op >> l >> r >> c;
        c = (c % mod + mod) % mod;
        if (op == 0) update_add (l, r, c);
        else if (op == 1) update_mul (l, r, c);
        else cout << query (r) << "\n";
    }
    return 0;
}