Недавно Вадику пришлось распрощаться с очередным игроком команды Team.GOV. Ему предстояло найти в команду нового игрока для участия в чемпионате Урала. Внезапно Вадик вспомнил, что на это соревнование допускаются сборные команды, а у него есть хорошая знакомая из Китая — Сяохун Хао, участница чемпионата мира про программированию. Отличный вариант! И вот он уже сидит за компьютером и строчит письмо.

Привет!

Я ищу игрока на чемпионат Урала. Не хочешь поиграть в команде Team.GOV? Если тебя интересует это предложение, вышли мне до завтра решение тестового задания.

Расстоянием Хэмминга между двумя строками равной длины называется количество символов, в которых различаются эти строки. Назовём расстоянием между строкой s₁ и более короткой строкой s₂ суммарное расстояние Хэмминга от строки s₂ до всех подстрок строки s₁, равных по длине строке s₂. Будем называть строку частичной, если в ней помимо символов алфавита может встречаться символ «?». Даны две частичные строки, требуется заменить в них знаки вопроса на символы алфавита так, чтобы расстояние между полученными строками было минимальным.

Тебе нужно решить эту задачу для случая, когда первая строка циклическая. Удачи!

P.S. Ах да! Строка называется циклической, когда для неё помимо обычных подстрок определены подстроки, равные конкатенации некоторого суффикса и некоторого префикса. Например, обычная строка «abcd» имеет две подстроки длины 3: «abc» и «bcd». А циклическая строка «abcd» дополнительно к тем двум имеет ещё две подстроки длины 3: «cd» + «a» = «cda», «d» + «ab» = «dab».

Конечно же, Вадим из уважения к Сяохун сделал тесты, строки в которых записаны не латинскими буквами, а иероглифами.

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

Замените в строках s и t знаки вопроса на иероглифы так, чтобы расстояние между полученными в результате этой замены строками было минимальным. Выведите искомое расстояние.

Нужно заменить знак вопроса в строке s на третий иероглиф, а знаки вопроса в строке t — на первый и второй иероглифы соответственно. Циклическая строка «21132» имеет подстроки «2113», «1132», «1322», «3221» и «2211». Расстояние Хэмминга от строки «3132» до этих подстрок равно соответственно трём, одному, трём, трём и четырём. Суммарное расстояние между строками равно четырнадцати.