Нам, в СКБ Контур приходится много работать. Поэтому иногда бывает не грех и отдохнуть, поиграть. Рассмотрим, например, вот такую очень известную игру для одного человека.

Есть поле размером 4×4. На нём расположены фишки, у которых одна сторона окрашена в белый цвет, а другая — в чёрный. Какие-то из них в данный момент лежат белой стороной вверх, какие-то вниз. За один ход можно перевернуть одну фишку и все соседние по горизонтали или вертикали с ней. Целью игры является позиция, в которой все фишки лежат одной стороной вверх (все чёрные либо все белые).

Естественно, такая игра быстро надоедает, неожиданных и нетипичных позиций становится всё меньше и меньше. Поэтому сейчас в СКБ Контур больше распространён модифицированный вариант игры. В этом варианте ход заключается в перекладывании фиксированной комбинации фишек, попадающей в квадрат 3×3. Например, ход может заключаться в переворачивании всех соседей выбранной фишки по диагонали.

Комбинация выбирается произвольной; её можно задать в виде поля 3×3, где центральная клетка соответствует той, в которую делается ход. Например на рисунке слева вверху показана комбинация для обычной игры, а внизу — для описанной в предыдущем абзаце. Заметим, что комбинация не обязана быть симметричной. Ход делается всегда в одну из клеток игрового поля (то есть центральная клетка квадрата 3×3, определяющего ход, выбирается из клеток поля). Предписания комбинации на переворачивание фишек, попадающих за пределы поля, игнорируются.

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

В первых четырёх строках описывается начальное расположение фишек. Символ 'W' — обозначает фишку, лежащую вверх белой стороной, символ 'B' — чёрной. В следующих трёх строках описывается ход — комбинация переворачиваемых фишек. '0' — фишку переворачивать не надо, '1' — надо.

Если добиться нужного расположения фишек невозможно, то выведите надпись «Impossible», иначе выведите минимальное количество ходов, за которое это расположение достигается.