eolymp
bolt
Try our new interface for solving problems
Problems

Морской бой

Морской бой

Time limit 2 seconds
Memory limit 64 MiB

После удачного рейда в залив Ли-Элль индейцы Воздушноногого Бизона и Проворной Мартышки захватили эскадру новейших судиславских военных кораблей. К сожалению, команды кораблей при бегстве успели унести с собой урановые стержни, и теперь корабли не могут сдвинуться с места.

Все корабли уже были разделены на два одинаковых отряда, каждый из которых находился в отдельной бухте. Каждая бухта имела форму квадрата со стороной один километр, разделённый на 100 одинаковых квадратов размером 100×100 метров. Бывают корабли следующих классов:

  • линкоры шириной в 100 метров и длиной в 400 метров;

  • дредноуты размерами 100×300 метров;

  • эсминцы размерами 100×200 метров;

  • экранолёты размерами 100×100 метров.

Обнаружив, что арсеналы кораблей полны, вожди решили на следующее утро провести боевые учения между отрядами: по очереди стрелять навесом в чужую бухту. Многохитрая Мартышка отправила отряд своих воинов на пирогах, чтобы те разведали, где в бухте противника стоят корабли.

Оказалось, что в каждом из ста квадратов бухты либо абсолютно пусто, либо весь квадрат занят некоторым кораблём или его частью, причём никакие два квадрата с кораблями не касаются по стороне или углу. Кроме того, разведчики отметили, что именно находится в каждом квадрате бухты, но по пути уронили карту в воду, и часть отметок исчезла. Теперь им стыдно возвращаться к своему вождю с такой малой добычей, и они просят вас найти, какой максимальной длины корабль, который не изображён полностью на карте, может находится в бухте.

Input data

Во входном файле находится описание карты Мартышки - матрица 10×10. Каждый элемент матрицы соответствует квадрату бухты и содержит символ:

  • ' ' (пробел) - если информация об этом квадрате была утеряна;

  • '.' - если этот квадрат исследовали и в нём не оказалось корабля;

  • '*' - если этот квадрат исследовали и в нём оказалась часть некоторого корабля.

Гарантируется, что существует хотя бы один не отмеченный полностью корабль.

Output data

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

Examples

Input example #1
****......
........*.
....*...*.
.*......*.
.....**...
.*........
.*.*...*..
.*.....*..
... .*....
    ......
Output example #1
400
****......
........*.
....*...*.
.*......*.
.....**...
.*........
.*.*...*..
.*.....*..
... .*....
****......