Copying Data

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define bug(x) cout << #x << "  >>>>>>>  " << x << '\n'
#define _ << " , " <<
#define INF 0x3f3f3f3f
#define iii pair<pair<int, int>, int>
#define ii pair<int, int>
#define fi first
#define se second

struct ColorUpdate {
    set<iii> intervals;
    vector<ii> data;

    ColorUpdate() {
        intervals.insert( { {-INF, INF}, -1} );
    }

    void paint(int l, int r, int x, int y) {
        if(l > r) return;

        int color = data.size();
        data.push_back({x, y});

        auto a = prev(intervals.upper_bound({{l, INF}, INF}));
        auto b = prev(intervals.upper_bound({{r, INF}, INF}));

        int l1 = a->fi.fi, r1 = l - 1, c1 = a->se;
        int l2 = r + 1, r2 = b->fi.se, c2 = b->se;

        intervals.erase(a, next(b));

        if(l1 <= r1) intervals.insert({{l1, r1}, c1});
        if(l2 <= r2) intervals.insert({{l2, r2}, c2});
        if(l <= r) intervals.insert({{l, r}, color});
    }

    int get_color_of(int x) {
        return prev(intervals.upper_bound({{x, INF}, INF}))->se;
    }

    ii get_pos(int i) {
        int col = get_color_of(i);
        if(col == -1) return {1, i};
        return {0, data[col].fi - data[col].se + i};
    }
};

int32_t main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;

    cin >> n >> q;

    vector<vector<int>> data(2, vector<int>(n));

    for(int i = 0; i < 2; i++)
        for(int j = 0; j < n; j++)
            cin >> data[i][j];

    ColorUpdate C;

    for(int i = 0; i < q; i++) {
        int o;
        cin >> o;
        if(o == 1) {
            int x, y, k;
            cin >> x >> y >> k; x--; y--;
            C.paint(y, y + k - 1, x, y);

        } else {
            int x;
            cin >> x; x--;
            auto [a, b] = C.get_pos(x);
            cout << data[a][b] << '\n';
        }
    }

    return 0;
}