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