H. Циклическая сортировка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два массива целых чисел $$$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$$$ последовательных операций над массивами. А именно, для каждого целого $$$i$$$ от $$$0$$$ до $$$k - 1$$$

  • если $$$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$$$.

Выходные данные

Для каждого набора тестов выведите две строки — состояния массивов $$$a_0, \ldots, a_{n - 1}$$$ и $$$b_0, \ldots, b_{m - 1}$$$ после выполнения $$$k$$$ операций, описанных выше.

Пример
Входные данные
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]