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