Информатика олимпиадная задача

Посадка в самолет
(Время: 1 сек. Память: 32 Мб Сложность: 24%)
В самолетах авиакомпании Битавиа кресла расположены в n рядов, при этом в каждом ряду по шесть мест, между третьим и четвертым местом находится проход. Некоторые пассажиры регистрируются заранее онлайн, другие пассажиры регистрируются на стойке регистрации в аэропорту.

При онлайн-регистрации пассажир может выбрать любое место и не может его затем менять. Например, при n = 6 рассадка в самолете после онлайн-регистрации может выглядеть так (крестиками отмечены занятые места):


На стойку регистрации придут m пассажиров. По правилам Битавиа нужно рассадить их в самолете таким образом, чтобы итоговая рассадка в самолете была симметрична относительно прохода. То есть, если в некотором ряду на первом кресле сидит пассажир, то в том же ряду на шестом кресле тоже должен сидеть пассажир. То же самое справедливо для второго и пятого, третьего и четвертого кресел, соответственно. При этом пересаживать пассажиров, прошедших онлайн-регистрацию нельзя. В исходную рассадку, показанную на рисунке выше, можно добавить семь пассажиров, удовлетворив условие симметрии, например, следующим образом:


Вам дана рассадка пассажиров после онлайн-регистрации. Требуется рассадить m пассажиров так, чтобы итоговая рассадка в самолете была симметрична относительно прохода, или определить, что это невозможно.

Входные данные
В первой строке входного файла INPUT.TXT содержатся два целых числа n и m — количество рядов в самолете и количество пассажиров, которые придут на стойку регистрации (1 ≤ n ≤ 1000, 0 ≤ m ≤ 6000).

В следующих n строках задана изначальная рассадка в самолете после онлайн-регистрации. В каждой строке содержится по шесть символов, при этом i-й символ j-й строки равен «X» (заглавная английская X), если i-е место в j-м ряду уже занято и «.» (точка) иначе.

Выходные данные
В выходной файл OUTPUT.TXT выведите «Impossible», если искомой рассадки не существует.

Иначе выведите n строк по шесть символов — итоговую рассадку в самолете. При этом i-й символ j-й строки должен быть равен «X», если место занято, и «.», если свободно. Если существует несколько решений, разрешается вывести любое