← 返回题目列表

Codeforces · 2161/H

H. 循环排序

中文机器翻译题面 查看原题

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

我们对数组执行 $$$k$$$ 操作。即,对于从 $$$0$$$ 到 $$$k - 1$$$ 的每个整数 $$$i$$$ 按此顺序

  • 如果 $$$a_{i \bmod n} \gt 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}$$$ 的状态。

示例

输入
复制

3
2 3 5
3 4
1 5 2
1 5 4
6
5 4 3 2 1
3 3 0
4 5 6
1 2 3

输出
复制

1 3
4 5 2
2
6 5 4 3 1
4 5 6
1 2 3

注意

第一个示例的操作序列

$$$i$$$$$$i \bmod n$$$$$$i \bmod m$$$比较行动数组 $$$a$$$数组 $$$b$$$
000$$$3 \gt 1$$$交换 $$$a_0$$$ 和 $$$b_0$$$[1, 4][3, 5, 2]
111$$$4 \lt 5$$$什么也没有[1, 4][3, 5, 2]
202$$$1 \lt 2$$$什么也没有[1, 4][3, 5, 2]
310$$$4 \gt 3$$$交换 $$$a_1$$$ 和 $$$b_0$$$[1, 3][4, 5, 2]
401$$$1 \lt 5$$$什么也没有[1, 3][4, 5, 2]