ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

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

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Определение. Расстоянием Хэмминга между двумя строками равной длины называется количество символов, в которых различаются эти строки.
Определение. Расстояние от текста s до шаблона p — это сумма всех хэмминговых расстояний от p до всех подстрок строки s, имеющих длину |p|.
Даны текст s и шаблон p. Одна из двух строк может быть повреждена (неизвестны некоторые символы), но не обе сразу. Требуется восстановить повреждённую строку так, чтобы расстояние от текста до шаблона стало минимально возможным.

Исходные данные

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

Результат

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

Пример

исходные данныерезультат
5
1 2 3 1 2
3
1 2 0
1 2 3 1 2
1 2 1
Автор задачи: Михаил Рубинчик (подготовка — Булат Зайнуллин)
Источник задачи: Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1959. GOV-стажировка 3