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