Посадка в самолет

В самолетах авиакомпании Битавиа кресла расположены в 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», если место занято, и «.», если свободно. Если существует несколько решений, разрешается вывести любое.

Примеры

Замечание

Выше приведены пять примеров входных данных.

1. В первом примере m = 0, а рассадка в самолете симметрична, поэтому итоговая рассадка совпадает с исходной.
2. Во втором примере есть только один способ рассадить пассажиров симметрично.
3. В третьем примере существовало бы решение, при m = 1, но при m = 2 не существует способа рассадить всех пассажиров симметрично.
4. В четвертом примере требуется рассадить больше пассажиров чем свободных мест в самолете.
5. Пятый примере соответствует ситуации, рассмотренной на рисунках в тексте условия. В этом примере существует несколько решений, приведено одно из них.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]