先把序列转 01，考虑对 01 序列编一些做法。
这里造成修改只能是 \(a_{t\bmod n}=1,b_{t\bmod m}=0\)，于是我们可以直接扔掉 \(a=0\) 和 \(b=1\) 的位。剩下每个 \(b_j=1\)，就是对于 \(t=j+cM\)，都有可能使 \(a_{t\bmod n}\leftarrow 0\)，对于一个 \(j\)，这样的修改只能进行一次。特别地，如果 \(a_i=0\)，我们认为有一个 \(t=-\infty\) 的修改。
一个想法是把这些修改挂到每个 \(a\) 上。具体地，对于初始 \(b_j=1\)，将修改挂到 \(j\bmod n\) 上。然后每次对于一个点 \(i\)，如果其上有 \(\ge 2\) 个标记，就把除最小值外的推到 \((i+m)\bmod n\)，并且把修改的时间 \(+m\)。如果一个修改的时间 \(\ge K\)，那么说明这个是不会有影响的，就可以直接确定 \(b=0\)。不妨把序列按 \(\bmod \gcd(n,m)\) 分类，然后按照 \(0,m\bmod n,\cdots,((n-1)m)\bmod n\) 的顺序重排，这样每次就是往后 \((i+1)\bmod n\)。
然后考虑怎么动态做。每次变化是把一个 \(1\to 0\)，也就是新增一个修改。可以发现，如果原来一个修改最终时刻会被推到 \(\ge K\)，那么它在之后也没用了。
考虑维护出所有有用的修改。记 \(c_i\) 为有多少个修改一开始被放在 \(i\)，那么向后推就是在做类似括号匹配的东西。取出前缀和 \(s_i=\sum\limits_{j\le i}(c_j-1)\)，整个序列会被非严格前缀 \(\min\) 划分为若干段，每段 \([l,r]\) 内是匹配的括号序列。同时可以发现，\(l\) 中时间最大的修改一定会被推到 \(r\) 匹配。
那么对于一个新增的修改，可以把它直接加入，判一下所在的段是否满足条件，不满足条件时把左端点处的时间最大的修改删除即可。这个可以线段树维护。复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int inf = 1e9;
const int kN = 2e5 + 5, kS = kN * 12;
int n, m, L;
ll K;
int a[kN], b[kN], c[kN], d[kN];
int va[kN], vb[kN], vc[kN], vd[kN];
int na[kN], rk[kN], ord[kN];
priority_queue<int> q[kN];struct Info {int mn, id;Info() { mn = 0, id = -1; }Info(int _mn, int _id) {mn = _mn;id = _id;}
};
Info operator + (Info x, Info y) {return Info(min(x.mn, y.mn),max((x.mn <= y.mn) ? x.id : -inf,(x.mn >= y.mn) ? y.id : -inf));
}#define ls (o << 1)
#define rs (o << 1 | 1)struct SGT {Info info[kS];int tag[kS];void Up(int o) { info[o] = info[ls] + info[rs]; }void Adt(int o, int t) { info[o].mn += t, tag[o] += t; }void Dn(int o) {if(int &t = tag[o]) {Adt(ls, t), Adt(rs, t), t = 0;}}void Init(int o, int l, int r) {tag[o] = 0;if(l == r) return void(info[o] = Info(-1 - l, l));int mid = (l + r) >> 1;Init(ls, l, mid);Init(rs, mid + 1, r);Up(o);}void Update(int o, int l, int r, int x, int y, int v) {if((l > y) || (r < x)) return ;if((l >= x) && (r <= y)) return Adt(o, v);Dn(o);int mid = (l + r) >> 1;Update(ls, l, mid, x, y, v);Update(rs, mid + 1, r, x, y, v);Up(o);}Info Query(int o, int l, int r, int x, int y) {if((l > y) || (r < x)) return Info(0, -1);if((l >= x) && (r <= y)) return info[o];Dn(o);int mid = (l + r) >> 1;return Query(ls, l, mid, x, y) + Query(rs, mid + 1, r, x, y);}int Find(int o, int l, int r, int x, int v) {if(info[o].mn > v) return r + 1;if(l == r) return r;Dn(o);int mid = (l + r) >> 1;if(mid < x) return Find(rs, mid + 1, r, x, v);int lft = Find(ls, l, mid, x, v);return (lft > mid) ? Find(rs, mid + 1, r, x, v) : lft;}
} sgt;void Work(int n, int m, int *a, int *b, int *c, int *d, ll K) {L = n + n + n;sgt.Init(1, 0, L);fill_n(q, n, priority_queue<int> ());for(int i = 0; i < n; i++) {int p = (ll)i * m % n;na[i] = a[p];rk[p] = i;ord[i] = p;}vector<pair<int, int>> vec;for(int i = 0; i < n; i++) {vec.emplace_back(a[i], i);}for(int i = 0; i < m; i++) {vec.emplace_back(b[i], i + n);}sort(vec.begin(), vec.end());auto Update = [&](int p, int v) {sgt.Update(1, 0, L, p, L, v);sgt.Update(1, 0, L, p + n, L, v);sgt.Update(1, 0, L, p + n + n, L, v);};auto AddToken = [&](int p, int tok) -> int {q[p].push(tok);Update(p, 1), p += n;Info info = sgt.Query(1, 0, L, 0, p - 1);int l = info.id + 1;int r = sgt.Find(1, 0, L, l, info.mn);int top = q[l % n].top();if((r <= L) && ((top == -inf) || (top + (ll)(r - l) * m < K))) {return -1 - r;}q[l % n].pop();Update(l % n, -1);return top;};for(auto k : vec) {int val, id, sq = 0;tie(val, id) = k;if(id >= n) id -= n, sq = 1;int p, tok;if(!sq) {p = rk[id], tok = -inf;}else {p = rk[id % n], tok = id;}int v = AddToken(p, tok);if(v >= 0) d[v] = val;else c[ord[(-1 - v) % n]] = val;}
}void Solve() {cin >> n >> m >> K;for(int i = 0; i < n; i++) cin >> a[i];for(int i = 0; i < m; i++) cin >> b[i];int g = __gcd(n, m);for(int r = 0; r < g; r++) {int cn = 0, cm = 0;for(int i = r; i < n; i += g) va[cn++] = a[i];for(int i = r; i < m; i += g) vb[cm++] = b[i];Work(cn, cm, va, vb, vc, vd, K / g + (K % g > r));for(int i = 0, j = r; i < cn; i++, j += g) {c[j] = vc[i];}for(int i = 0, j = r; i < cm; i++, j += g) {d[j] = vd[i];}}for(int i = 0; i < n; i++) {cout << c[i] << " \n" [i == n - 1];}for(int i = 0; i < m; i++) {cout << d[i] << " \n" [i == m - 1];}
}int main() {// freopen("1.in", "r", stdin);// freopen("1.out", "w", stdout);ios::sync_with_stdio(0), cin.tie(0);int t;cin >> t;while(t--) Solve();return 0;
}