Руді пси#1410
-- Хто йде там? -- запитав Фао (у джунглях це питання завжди ставлять після звуку сурми). -- Дхолі, дхолі, деканські дхолі! Червоні собаки! Вони прийшли з півдня, кажуть, у Декані немає здобичі.
Перед входом у долину Сеоні зграя голодних червоних собак вишикувалася у прямокутний бойовий порядок розміром N \times M собак. Диким гавкотом і гучним виттям вони привітали свого ватажка. Однак ватажок не був вражений такою какофонією; у нього були свої уявлення про те, як його повинні вітати.
Використовуючи свою владу, він може будь-яку кількість разів віддати наказ, щоб собаки у будь-якому підпрямокутнику бойового порядку розміром K \times L (де вертикальна сторона має довжину , а горизонтальна — ) перейшли з виття на гавкіт та з гавкоту на виття.
Чи зможе він досягти гармонійного привітання від своєї зграї?
Перший рядок вхідного файлу містить числа , , , (1 \leq N, M, K, L \leq 100,\ K \leq N,\ L \leq M).
У наступних рядках знаходиться по чисел, де означає, що собака гавкає, а — виє. Ці рядків задають початкову какофонію. У наступних рядках у такому ж форматі записане бажане гармонійне привітання.
У вихідному файлі має бути записано найменшу кількість команд, які ватажкові потрібно віддати, щоб досягти гармонійного привітання, або , якщо таку послідовність команд отримати неможливо.
Приклад 1