H. Cycle Sort
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Input

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

Output

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.

Example
Input
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
Output
1 3 
4 5 2 
2 
6 5 4 3 1 
4 5 6 
1 2 3
Note

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]