eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

GOV-стажировка 3

GOV-стажировка 3

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Определение. Расстоянием Хэмминга между двумя строками равной длины называется количество символов, в которых различаются эти строки.

Определение. Расстояние от текста s до шаблона p - это сумма всех хэмминговых расстояний от p до всех подстрок строки s, имеющих длину |p|.

Даны текст s и шаблон p. Одна из двух строк может быть повреждена (неизвестны некоторые символы), но не обе сразу. Требуется восстановить повреждённую строку так, чтобы расстояние от текста до шаблона стало минимально возможным.

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

В первой строке записана длина n (1 n 100000) текста s. Во второй строке записан текст s в виде n целых неотрицательных чисел через пробел. В третьей строке записана длина m шаблона p (1 m < n). В четвёртой строке записан шаблон p в аналогичном формате. Положительные числа обозначают номера их символов в алфавите, а ноль - повреждённый символ. Числа, обозначающие номера символов, не превосходят 100000.

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

Выведите в первой строке текст, а во второй строке - шаблон, восстановив повреждённую строку так, чтобы расстояние между строками стало минимально возможным. Если есть несколько способов восстановления, выведите любое.

Пример

Входные данные #1
5
1 2 3 1 2
3
1 2 0
Выходные данные #1
1 2 3 1 2
1 2 3
Автор М.Рубинчик, Б.Зайнуллин
Источник 2013 Петрозаводск, Зима, Контест Уральского университета, Кубок Контура, Задача I