«Тайная комната снова открыта» — эта новость распространилась по всему Хогвартсу. Дамблдор был уволен и теперь Гарри пытается попасть в тайную комнату. Лорд Волдеморт не доволен таким развитием событий, он хочет помешать Гарри.

Тайная комната представляет собой прямоугольное поле n × m, в некоторых клетках которого стоят колонны. Колонны обладают необычным свойством: луч света может беспрепятственно проходить сквозь них, не меняя своего направления. Используя магию, можно превратить некоторые колонны в магические. Магические колонны отличаются от обычных тем, что луч света, проходящий через магическую колонну, отражается в четыре стороны как показано на рисунке.

Слева свет проходит через обычную колонну, справа — через магическую.

Василиск находится на правой стороне правой нижней клетки поля и смотрит налево (в сторону левой нижней клетки). Как гласит легенда, тот, кто посмотрит прямо в глаза Василиску, сразу умирает. А тот, кто посмотрит в глаза Василиску через колонну, окаменеет. Мы знаем, что дверь в тайную комнату находится на левой стороне левой верхней клетки поля, а также что любой заходящий в комнату человек обязательно будет смотреть по направлению своего движения (то есть в сторону правой верхней клетки).

На рисунке изображен первый тестовый пример.

Вам заданы размеры тайной комнаты и позиции колонн. Лорд Волдеморт попросил вас найти минимальное количество колонн, которое нужно сделать магическими, чтобы любой, кто вошел в тайную комнату, немедленно окаменел, или сказать, что задуманное сделать невозможно.