Мутація
Вчені планети Олімпія проводять експеримент з генної мутації піддослідного примітивного організму в цільовий примітивний організм. Геноми організмів можуть бути представлені у вигляді послідовності генів, а кожен ген кодується цифрою 0 чи 1. Експеримент проводиться поетапно. На кожному етапі у геномі піддослідного організму деякі гени змінюються на протилежні (тобто, з 0 на 1 та навпаки). Вчені можуть обирати які саме гени змінювати, але їх кількість на кожному з етапів фіксована. Ця кількість обумовлена біологічно і задана для кожного етапу мутації окремо. Геноми піддослідного і цільового примітивних організмів складаються з однакової кількості генів. Відомо, що геноми складаються з певної кількості повторень однієї й тої самої послідовності генів, яка називається базовою.
Напишіть програму, яка за заданими геномами піддослідного та цільового примітивних організмів, а також за кількостями генів, що змінюються на кожному з етапів експерименту знайде найменшу кількість етапів мутації генома піддослідного організму до геному цільового організму.
Вхідні дані
Перший рядок містить чотири цілих числа A, B, N та M (1 ≤ A ≤ 40000, 1 ≤ B ≤ 40000, 1 ≤ N ≤ 2×10^9, 1 ≤ M ≤ 100000). A, B - довжини базових послідовностей генів відповідно піддослідного та цільового примітивних організмів. Число N - довжина геномів обох організмів; гарантується, що число N націло ділиться і на A, і на B. Число M – максимальна кількість етапів мутації, які вчені можуть провести. Другий і третій рядки містять базові послідовності для піддослідного та цільового примітивних організмів, складаються лише з 0 та 1 і мають довжини A та B відповідно. i-ий з наступних M рядків містить натуральне число, що не перевищує N – кількість генів, що буде змінено на i-му етапі. Гарантовано, що мутацію можна завершити за M, або за меншу кількість етапів.
Вихідні дані
Вивести одне ціле число – шукану мінімальну кількість етапів мутації, за яку вченим вдасться отримати геном цільового організму з геному піддослідного.