给定两个整数数组 $$$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}$$$ 的状态。
示例
输入复制
32 3 53 41 5 21 5 465 4 3 2 13 3 04 5 61 2 3
输出复制
1 34 5 226 5 4 3 14 5 61 2 3
注意
第一个示例的操作序列
| $$$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] |