CF2161H Cycle Sort

You are given two integer arrays $ a_0, \ldots, a_{n - 1} $ and $ b_0, \ldots, b_{m - 1} $ . Each integer among $ 1, \ldots, n + m $ is present exactly once among $ a_0, \ldots, a_{n - 1}, b_0, \ldots, b_{m - 1} $ . We perform $ k $ operations on the arrays. Namely, for each integer $ i $ from $ 0 $ to $ k - 1 $ in this order - if $ a_{i \bmod n} > b_{i \bmod m} $ , we swap $ a_{i \bmod n} $ and $ b_{i \bmod m} $ - otherwise, we do nothing Determine the final state of both arrays after all $ k $ operations are completed.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains three integers $ n, m, k $ ( $ 1 \leq n, m \leq 2 \cdot 10^5 $ , $ 0 \leq k \leq 10^{18} $ ). The second line contains $ n $ integers $ a_0, \ldots, a_{n - 1} $ . The third line contains $ m $ integers $ b_0, \ldots, b_{m - 1} $ . It is guaranteed that the joint sequence $ a_0, \ldots, a_{n - 1}, b_0, \ldots, b_{m - 1} $ is a permutation of integers from $ 1 $ to $ n + m $ . The sum of $ n + m $ over all testcases doesn't exceed $ 2 \cdot 10^5 $ .

For each testcase, print two lines — the states of the arrays $ a_0, \ldots, a_{n - 1} $ and $ b_0, \ldots, b_{m - 1} $ after the $ k $ operations are performed as described above.

The action sequence for the first example $ i $ $ i \bmod n $ $ i \bmod m $ comparisonactionarray $ a $ array $ b $ 000 $ 3 \gt 1 $ swap $ a_0 $ and $ b_0 $ \[1, 4\]\[3, 5, 2\]111 $ 4 \lt 5 $ nothing\[1, 4\]\[3, 5, 2\]202 $ 1 \lt 2 $ nothing\[1, 4\]\[3, 5, 2\]310 $ 4 \gt 3 $ swap $ a_1 $ and $ b_0 $ \[1, 3\]\[4, 5, 2\]401 $ 1 \lt 5 $ nothing\[1, 3\]\[4, 5, 2\]