Определение. Расстоянием Хэмминга между двумя строками равной длины называется количество символов, в которых различаются эти строки.

Определение. Расстояние от текста s до шаблона p — это сумма всех хэмминговых расстояний от p до всех подстрок строки s, имеющих длину |p|.

Даны текст s и шаблон p. Одна из двух строк может быть повреждена (неизвестны некоторые символы), но не обе сразу. Требуется восстановить повреждённую строку так, чтобы расстояние от текста до шаблона стало минимально возможным.

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

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