ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2143. Victoria!

Ограничение времени: 0.5 секунды
Ограничение памяти: 256 МБ
Представьте, что Вы работаете главным программистом в известной авиакомпании VictoriAir. Эта компания появилась относительно недавно, но уже бьёт все мировые рекорды по количеству пассажиров в год. Всё благодаря нестандартному мышлению и индивидуальному подходу к каждому клиенту.
Расскажем об одной из особенностей VictoriAir. Довольно очевидно, что если несколько человек покупают билеты вместе, скорее всего это родственники, друзья или коллеги, то есть люди, которые часто проводят время вместе. Аналитики VictoriAir прекрасно это понимают и считают, что люди, которые покупают билеты вместе, не должны сидеть на соседних местах. Действительно, ведь в современном мире так мало возможностей побыть наедине со своими мыслями. Вам, как главному программисту, выпала честь реализовать эту функцию.
Салон самолёта VictoriAir представляет собой несколько рядов, в каждом ряду шесть кресел. Ряды нумеруются, начиная с единицы. В каждом ряду кресла нумеруются слева направо буквами A, B, C, D, E, F. Номер места — это номер ряда и буква, которая соответствует креслу, например, 11A, 21F, и т.д. В каждом ряду между креслами C и D расположен широкий проход. Два места называются соседними, если они находятся с одной стороны от прохода, а номер ряда и буква отличается не более чем на один. Например, места 1A и 2B являются соседними, а места 1A и 1C — нет. Вы знаете, какие места в салоне уже заняты. Необходимо рассадить группу из k человек так, чтобы никакие два из них не сидели рядом.

Исходные данные

В первой строке через пробел даны два целых числа n и k — количество рядов в салоне самолёта и количество людей, купивших билеты вместе, соответственно (1 ≤ n ≤ 100, 1 ≤ k ≤ 6 · n).
Далее следуют n строк, каждая из которых содержит описание очередного ряда — строку длины 9 символов. Символ «.» (код 46) означает, что кресло свободно, «*» (код 42) — что занято. Первые три символа описывают занятость мест A,B,C. Затем следуют ещё три символа «|_|» (коды 124, 95, 124; без кавычек) — описание прохода между креслами. Последние три символа описывают занятость мест D,E,F.
Гарантируется, что число k не превосходит количество свободных мест в салоне.

Результат

Если рассадить всех людей нужным способом невозможно, в единственной строке выведите слово «PORAZHENIE» (без кавычек). Иначе в первой строке выведите слово «POBEDA» (без кавычек), затем в следующих k строках выведите номера мест, на которые нужно посадить людей, в любом порядке. Номера мест следует выводить в формате, описанном в условии. Если возможных ответов несколько, выведите любой.

Примеры

исходные данныерезультат
2 2
.**|_|**.
**.|_|***
POBEDA
1A
2C
2 3
...|_|***
***|_|***
PORAZHENIE
Автор задачи: Алексей Кунгурцев
Источник задачи: Уральская командная олимпиада по программированию 2019