GOV-стажування 3#5617
Визначення. Відстанню Хеммінга між двома рядками однакової довжини називається кількість символів, у яких відрізняються ці рядки.
Визначення. Відстань від тексту до шаблону — це сума усіх хеммінгових відстаней від до усіх підрядків рядка , які мають довжину .
Задано текст та шаблон . Один з двох рядків може бути пошкодженим (невідомі деякі символи), але не обидва відразу. Потрібно відновити пошкоджений рядок так, щоб відстань від тексту до шаблону стала мінімально можливою.
У першому рядку записано ціле число — довжина тексту (1 \le n \le 100000). У другому рядку записано текст у вигляді цілих невід'ємних чисел через пропуск. У третьому рядку записано ціле число — довжина шаблону (1 \le m < n). У четвертому рядку записано шаблон у аналогічному форматі. Додатні числа позначають номери цих символів у алфавіті, а нуль — пошкоджений символ. Числа, які позначають номери символів, не перевищують .
Виведіть у першому рядку текст, а у другому рядку — шаблон, відновивши пошкоджений рядок так, щоб відстань між рядками стала мінімально можливою. Якщо є декілька способів відновлення, виведіть довільний.
Приклад 1