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} \gt 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.

给你两个整数数组 $a_0, \ldots, a_{n - 1}$ 和 $b_0, \ldots, b_{m - 1}$。在 $a_0, \ldots, a_{n - 1}, b_0, \ldots, b_{m - 1}$ 中，$1, \ldots, n + m$ 中的每个整数恰好出现一次。

我们对这两个数组执行 $k$ 次操作。具体来说，按顺序对每个从 $0$ 到 $k - 1$ 的整数 $i$ 执行以下操作：

• 若 $a_{i \bmod n} \gt b_{i \bmod m}$，则交换 $a_{i \bmod n}$ 与 $b_{i \bmod m}$；
• 否则，不进行任何操作。

请确定在完成全部 $k$ 次操作后，两个数组的最终状态。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

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.

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

The action sequence for the first example

$i$

$i \bmod n$

$i \bmod m$

comparison

action

array $a$

array $b$

0

0

0

$3 \gt 1$

swap $a_0$ and $b_0$

[1, 4]

[3, 5, 2]

1

1

1

$4 \lt 5$

nothing

[1, 4]

[3, 5, 2]

2

0

2

$1 \lt 2$

nothing

[1, 4]

[3, 5, 2]

3

1

0

$4 \gt 3$

swap $a_1$ and $b_0$

[1, 3]

[4, 5, 2]

4

0

1

$1 \lt 5$

nothing

[1, 3]

[4, 5, 2]

第一个示例的动作序列

$i$

$i \bmod n$

$i \bmod m$

比较

动作

数组 $a$

数组 $b$

0

0

0

$3 \gt 1$

交换 $a_0$ 和 $b_0$

[1, 4]

[3, 5, 2]

1

1

1

$4 \lt 5$

无操作

[1, 4]

[3, 5, 2]

2

0

2

$1 \lt 2$

无操作

[1, 4]

[3, 5, 2]

3

1

0

$4 \gt 3$

交换 $a_1$ 和 $b_0$

[1, 3]

[4, 5, 2]

4

0

1

$1 \lt 5$

无操作

[1, 3]

[4, 5, 2]