CF2161H Cycle Sort

给定两个整数数组 $a_0, \ldots, a_{n - 1}$ 和 $b_0, \ldots, b_{m - 1}$。在 $a_0, \ldots, a_{n - 1}, b_0, \ldots, b_{m - 1}$ 这 $n+m$ 个数中，$1$ 到 $n+m$ 的每个整数各出现恰好一次。 我们对这两个数组进行 $k$ 次操作。具体地，对于每个整数 $i$，从 $0$ 到 $k-1$ 依次进行以下操作： - 如果 $a_{i \bmod n} > b_{i \bmod m}$，则交换 $a_{i \bmod n}$ 和 $b_{i \bmod m}$； - 否则，不进行操作。 请你在 $k$ 次操作全部完成后，输出两个数组的最终状态。

每组测试数据包含多个测试用例。第一行包含测试用例的个数 $t$（$1 \le t \le 10^4$）。每组测试用例描述如下。 每个测试用例第一行包含三个整数 $n, m, k$（$1 \leq n, m \leq 2 \cdot 10^5$，$0 \leq k \leq 10^{18}$）。 第二行包含 $n$ 个整数 $a_0, \ldots, a_{n-1}$。 第三行包含 $m$ 个整数 $b_0, \ldots, b_{m-1}$。 保证 $a_0, \ldots, a_{n-1}, b_0, \ldots, b_{m-1}$ 联合起来是 $1$ 到 $n+m$ 的一个排列。 所有测试用例中 $n+m$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试用例，输出两行，分别为 $k$ 次操作之后数组 $a_0, \ldots, a_{n-1}$ 和 $b_0, \ldots, b_{m-1}$ 的状态。

第一个样例的操作过程如下： \[ \begin{array}{cccccccc} i & i \bmod n & i \bmod m & \text{比较} & \text{操作} & \text{数组 } a & \text{数组 } b \\ 0 & 0 & 0 & 3 > 1 & 交换 a_0 与 b_0 & [1, 4] & [3, 5, 2] \\ 1 & 1 & 1 & 4 < 5 & 无操作 & [1, 4] & [3, 5, 2] \\ 2 & 0 & 2 & 1 < 2 & 无操作 & [1, 4] & [3, 5, 2] \\ 3 & 1 & 0 & 4 > 3 & 交换 a_1 与 b_0 & [1, 3] & [4, 5, 2] \\ 4 & 0 & 1 & 1 < 5 & 无操作 & [1, 3] & [4, 5, 2] \\ \end{array} \] 由 ChatGPT 5 翻译