Рабочее место участника

Недавно программист Антон узнал о существовании игры "Тетрис++". Игра очень похожа на обычный, всем привычный тетрис, но есть несколько отличий.

Правила игры "Тетрис++":

Игровое поле представляет собой клетчатое поле высотой `N` и шириной `M` квадратиков, на дне которого могут находиться квадратики разных цветов. В начале игры из левого верхнего угла начинает падать фигурка, имеющая вид вертикального прямоугольника размера 3х1, каждый из квадратиков которого окрашен в некоторый цвет.

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

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

Цель игры оставить на доске минимально возможное количество цветных квадратиков. Помогите Антону определить, на сколько позиций нужно переместить падающую фигурку вправо и сколько раз циклически её сдвинуть вверх, чтобы в конце концов на поле осталось как можно меньше квадратиков.

В первой строке расположены числа `N` и `M`, разделённые пробелом (`4\ ≤\ N\ ≤\ 26`, `1\ ≤\ M\ ≤\ 15`).

В каждой из следующих `N` строк расположены по `M` чисел, разделённых пробелами, описывающих начальное состояние игрового поля (сверху вниз). Числа от 1 до 9 при этом обозначают цвет соответствующего квадратика, а число 0 – отсутствие цветного квадратика в данном месте игрового поля. В последних трёх строках расположены три числа – цвета (от 1 до 9) квадратиков (сверху вниз) падающей фигурки.

Гарантируется, что верхние 4 ряда игрового поля не содержат цветных квадратиков.

Требуется вывести 3 числа, отделенных друг от друга пробелами. Первое число – количество единиц, на которое требуется передвинуть фигурку вправо (от 0 до `M\ -\ 1`). Второе число – требуемое количество циклических сдвигов (от 0 до 2). Третье – суммарное количество исчезнувших в результате падения этой фигурки квадратиков. Если оптимальных решений больше одного, должно быть выведено решение с минимальным числом перемещений фигурки вправо, а если таких решений несколько, решение с минимальным числом перемещений фигурки и минимальным сдвигом.

6 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
1 0 1 1 0 0
1
1
1

1 0 6

8 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 1 0 0 0
0 2 3 1 0 0
0 4 2 3 3 0
5 4 5 4 5 1
3
2
1

0 1 10