Морской бой
После удачного рейда в залив Ли-Элль индейцы Воздушноногого Бизона и Проворной Мартышки захватили эскадру новейших судиславских военных кораблей. К сожалению, команды кораблей при бегстве успели унести с собой урановые стержни, и теперь корабли не могут сдвинуться с места.
Все корабли уже были разделены на два одинаковых отряда, каждый из которых находился в отдельной бухте. Каждая бухта имела форму квадрата со стороной один километр, разделённый на 100 одинаковых квадратов размером 100×100 метров. Бывают корабли следующих классов:
линкоры шириной в 100 метров и длиной в 400 метров;
дредноуты размерами 100×300 метров;
эсминцы размерами 100×200 метров;
экранолёты размерами 100×100 метров.
Обнаружив, что арсеналы кораблей полны, вожди решили на следующее утро провести боевые учения между отрядами: по очереди стрелять навесом в чужую бухту. Многохитрая Мартышка отправила отряд своих воинов на пирогах, чтобы те разведали, где в бухте противника стоят корабли.
Оказалось, что в каждом из ста квадратов бухты либо абсолютно пусто, либо весь квадрат занят некоторым кораблём или его частью, причём никакие два квадрата с кораблями не касаются по стороне или углу. Кроме того, разведчики отметили, что именно находится в каждом квадрате бухты, но по пути уронили карту в воду, и часть отметок исчезла. Теперь им стыдно возвращаться к своему вождю с такой малой добычей, и они просят вас найти, какой максимальной длины корабль, который не изображён полностью на карте, может находится в бухте.
Входные данные
Во входном файле находится описание карты Мартышки - матрица 10×10. Каждый элемент матрицы соответствует квадрату бухты и содержит символ:
' ' (пробел) - если информация об этом квадрате была утеряна;
'.' - если этот квадрат исследовали и в нём не оказалось корабля;
'*' - если этот квадрат исследовали и в нём оказалась часть некоторого корабля.
Гарантируется, что существует хотя бы один не отмеченный полностью корабль.
Выходные данные
В первой строке выведите целое число - максимально возможную длину в метрах не обнаруженного полностью корабля в бухте учебного врага. В следующих строках выведите карту Мартышки в том же формате, что и во входном файле, на которую символами '*' добавлено возможное расположение корабля указанной длины. Если решений несколько, выведите любое из них.