Плохой Санта
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В небольшом классе ученики организовали игру «Тайный Санта». Каждый ученик зарегистрировался на сайте SecretSanta, где случайным образом получил имя того, кому нужно подарить подарок. Жеребьёвка завершилась успешно, и все участники узнали, кого им нужно поздравить.

Но внезапно появилась проблема: некоторые ученики решили стать плохишами и отказались дарить подарки. Перед праздником магическая сова принесла письмо с именами плохишей детей. Теперь праздник под угрозой, так как подарки могут оказаться у тех, кто их не заслуживает.

Ваша задача — перераспределить список дарителей и получателей подарков так, чтобы:

- Каждый хороший ребёнок дарил подарок только хорошему.
- Каждый плохиш дарил подарок только плохишу.
- Количество изменений в первоначальном списке было минимальным.

Помогите пересчитать пары дарителей и получателей, чтобы Рождество состоялось!

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$4 \leq n \leq 10^5$$$) — количество детей.

В следующей строке находятся $$$n$$$ чисел $$$p_i$$$ ($$$1 \leq p_i \leq n$$$, $$$p_i \neq i$$$). Каждое $$$p_i$$$ обозначает ребёнка, которому дарит подарок $$$i$$$-й ребенок. Гарантируется, что каждый ребенок получит только один подарок, и ни один ребенок не дарит подарок самому себе.

В следующей строке находится одно число $$$m$$$ ($$$2 \leq m \leq n - 2$$$) — количество плохишей.

В следующей строке находятся $$$m$$$ попарно различных чисел $$$a_i$$$ ($$$1 \leq a_i \leq n$$$) — список детей, которые решили не дарить подарки.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

В единственной строке выведите $$$n$$$ чисел $$$p_i$$$ — новый список, где каждое $$$p_i$$$ обозначает ребёнка, которому дарит подарок $$$i$$$-й ребенок.

Каждый ребенок согласно списку должен получить ровно один подарок, и ни один ребенок не должен дарить подарок самому себе.

Можно показать, что в указанных ограничениях это всегда возможно сделать.

Пример

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

    363 4 2 1 6 544 3 2 566 1 4 2 3 533 2 663 4 2 1 6 533 5 6

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

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

Примечание

Разберём первый набор входных данных первого теста:

Изначальный список в примере

Изменённый список