Мальчику Васе очень нравится известная игра «Сапер». В нее играет один человек. Игра идет на клетчатом поле размером \(m\)×\(n\) (\(m\) строк, \(n\) столбцов). В некоторых клетках поля стоят мины. В каждой из остальных клеток записано либо число от 1 до 8 – количество мин в соседних с ней клетках, либо ничего не написано – это означает, что в соседних клетках мин нет. Клетки являются соседними, если они имеют хотя бы одну общую вершину. В одной клетке не может стоять более одной мины. Будем называть поле с расположенными на нем минами и числами картой.

Изначально все клетки поля закрыты. Игрок за один ход может открыть какую-нибудь клетку. После этого игроку показывается содержимое этой клетки, и если в открытой им клетке оказывается мина, он проигрывает. В противном случае игра продолжается. Цель игры – открыть все клетки, в которых нет мин.

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

У Васи есть рисунки, нарисованные на клетчатой бумаге следующим образом: некоторые клетки закрашены в черный цвет, а некоторые оставлены белыми. Вася хочет по каждому такому рисунку сделать соответствующее ему поле для игры в «Сапера» по следующему правилу: если на рисунке клетка покрашена в черный цвет, то на этом месте должна быть либо мина, либо число от 1 до 8, если же клетка оставлена белой, то на игровом поле она должна быть пустой.

Напишите программу, которая сделает это за Васю.

Недавно один известный художник-абстракционист произвел на свет новый шедевр – картину «Два черных непересекающихся прямоугольника». Картина представляет собой прямоугольник \(m\)×\(n\), разбитый на квадраты 1×1, некоторые из которых закрашены любимым цветом автора – черным. Федя – не любитель абстрактных картин, однако ему стало интересно, действительно ли на картине изображены два непересекающихся прямоугольника. Помогите ему это узнать. Прямоугольники не пересекаются в том смысле, что они не имеют общих клеток.

На столе лежат n монеток. Некоторые из них лежат вверх решкой, а некоторые – гербом. Определите минимальное число монеток, которые нужно перевернуть, чтобы все монетки были повернуты вверх одной и той же стороной.

Вы, наверное, замечали, что многие компании используют для рекламы «красивые» номера телефонов, которые удобны для запоминания потенциальными клиентами. Но что делать, если номер вашей компании ничем не примечателен? Можно присмотреться к нему повнимательнее, а вдруг, если перегруппировать цифры номера некоторым образом, номер станет намного красивее? Например, если у вашей компании номер 872-73-33, то его можно сделать красивее, если перегруппировать цифры так: 8727-333.

Введем следующую оценку красоты разбиения номера. Будем разбивать номер дефисами на группы размером от 2 до 4 цифр. Теперь красотой разбиения назовем сумму баллов, которые приносит каждая группа. Эти баллы будем считать, пользуясь следующей таблицей.

	 
Шаблон группы          Баллы	 
aa                     2	 
aba                    2	 
aab, abb               2	 
aaa                    3	 
abac, baca             2	 
abab                   3	 
aabb                   3	 
abba                   4	 
baaa, abaa, aaba, aaab 3	 
aaaa                   5

В этой таблице символами «a», «b», «c» обозначены различные цифры. Например под шаблон «aab» подходят группы «223», «667», но не подходят «123» и «888».

Пользуясь предложенной оценкой, найдите наиболее красивое разбиение заданного номера.