Фантасмагорія

Сни в Еміля часто наповнені людьми чи тваринами, які перетворюються одне в одного. Еміль хоче показати всім чарівний світ своїх снів, створивши найперший анімаційний фільм, звісно ж, чорно-білий. Проте, прокинувшись, Еміль пам'ятає лише початкову й кінцеву форми, що з'явились у його сні, а не саме перетворення, тож просить вас відтворити ці «морфування», детально описавши кроки, які ведуть від першого зображення до другого.

Зображення у снах Еміля не є просто будь-якими чорно-білими малюнками; вони підпорядковуються таким трьом обмеженням.

По-перше, всі пікселі на межі зображення — найлівіший і найправіший стовпці, а також верхній і нижній ряди — мають однаковий колір.

По-друге, зображення не містить жодного квадрата 2 \times 2 вигляду

Третє обмеження складніше й формулюється наступним чином. Розбийте зображення на області, де область — це зв'язна однотонна ділянка, тобто найтонший розподіл такий, що будь-які два сусідні пікселі одного кольору належать одній області. Дві області вважаються сусідніми, якщо містять суміжні пікселі. У зображеннях Еміля кожна область межує не більш ніж із двома іншими областями, а область, що містить прикордонні пікселі, межує не більш ніж з однією іншою областю.

Вам дано два чорно-білих зображення розміру w \times h, і ваша мета — знайти «морфування», яке перетворить перше зображення в друге. Морфуванням із зображення $A$ у зображення $B$ називається послідовність зображень, яка починається з $A$ і закінчується $B$, така що:

• кожне зображення (крім першого) отримується з попереднього перевертанням одного біта;

• кожне зображення задовольняє трьом вищезазначеним обмеженням;

• під час морфування кількість областей кожного кольору не змінюється.