Тетрис
Недавно программист Антон узнал о существовании игры "Тетрис++". Игра очень похожа на обычный, всем привычный тетрис, но есть несколько отличий.
Правила игры "Тетрис++":
Игровое поле представляет собой клетчатое поле высотой N и шириной M квадратиков, на дне которого могут находится квдратики разных размеров. В начале игры из левого верхнего угла начинает падать фигурка, имеющая вид вертикального прямоугольника размером 3×1, каждый из квадратиков которого окрашен в некоторый цвет.
В момент появления фигурки на доске игрок может моментально сдвинуть её на произвольное целое количество клеточек вправо и сдвинуть клеточки фигурки циклически вверх произвольное количество раз. Дальше фигурка падает вниз до тех пор, пока не "встаёт" на лежащий квадратик или на дно игрового поля.
После падения фигурки начинается самое интересное: всевозможные последовательности, состоящие из не менее чем 3 квадратиков одного цвета, лежащих подряд на одной вертикали, горизонтали или диагонали, одновременно мгновенно исчезают. Все цветные квадратики, расположенные выше исчезнувших, мгновенно и одновременно падают вниз. Если после падения образуются новые последовательности из 3 и более квадратиков одного цвета, то они одновременно исчезают и так далее.
Цель игры оставить на доске минимально возможное количество цветных квадратиков.
Помогите Антону определить, на сколько позиций нужно переместить падающую фигурку вправо и сколько раз её циклически сдвинуть вверх, чтобы в конце концов на поле осталось как можно меньше квадратиков.
Входные данные
В первой строке расположены числа N и M, разделённые пробелом (4 ≤ N ≤ 26, 1 ≤ M ≤ 15). В каждой из последующих N строк расположены по M чисел, разделённых пробелами, описывающих начальное состояние игрового поля (сверху вниз). Числа от 1 до 9 при этом обозначают цвет соответствующего квадратика, а число 0 - отсутствие цветного квадратика на данном месте игрового поля. В последних трёх строках расположены три числа - цвета (от 1 до 9) квадратиков (сверху вниз) падающей фигурки.
Гарантируется, что верхние четыре ряда игрового поля не содержат цветных квадратиков.
Выходные данные
Требуется вывести 3 числа, отделённых друг от друга пробелами. Первое число - количество единиц, на которые требуется подвинуть фигурку вправо (от 0 до M-1). Второе число - требуемое число циклических сдвигов (от 0 до 2). Третье - суммарное количество исчезнувших в результате падения фигурки квадратиков. Если оптимальных решений больше одного, должно быть выведено решение с минимальным числом перемещений фигурки вправо, а если и таких решений несколько, решение с минимальным числом перемещений фигурки и минимальным сдвигом.