Imagine being a senior programmer in a famous airline VictoriAir. This airline is relatively young, but it already has the most passengers per year. It’s all because of creative thinking and individual approach to every client.
Let’s look at one interesting feature of VictoriAir. It’s obvoius that a group of people buying tickets together are likely to be relatives, frends or co-workers, in other words, people who spend a lot of time together. Analysts of VictoriAir understand it and consider that people in a group shouldn’t sit nearby. Indeed, there are so few opportunities to be alone with your own thoughts in the modern world. As the senior programmer, you are to implement this functionality.
The cabin of a VictoriAir plane has n rows, each row contains 6 seats. In each row, seats are named left to right with letters A, B, C, D, E, F. The number of a seat is the number of it’s row and the letter corresponding to the seat, for example, 11A, 21F, etc. In each row, seats C and D are separated by an aisle. Two seats are considered adjacent, if they are located on the same side from the aisle, and both their numbers of row and letters differ by at most one. For example, seats 1A and 2B are adjacent, and seats 1A and 1C aren’t. You know which seats are already occupied. You need to choose seats for a group of k people so that neither two of them are adjacent.
The first line contains two integers, separated with spaces: n and k — the amount of rows in the plane and the amount of people bying tickets together (1 ≤ n ≤ 100, 1 ≤ k ≤ 6 · n).
Each of next n lines describe a row in the cabin. They consist of exactly 9 characters. Character “
.” (code 46) denotes an empty seat, character “
*” (code 42) denotes an occupied seat. The first three characters represent seats A, B and C. Then, three characters “
|_|” follow (codes 124, 95, 124; without quotes), representing the aisle. The last three characters represent seats D, E and F.
It is guaranteed that k does not exceed the amount of empty seats in the cabin.
If it’s impossible to assign seats to all k people so that neither two of them are adjacent, output the word “
PORAZHENIE” (without quotes) in the first and only line. Otherwise, output the word “
POBEDA” (without quotes) in the first line, and then output k more lines, each containing a number of a seat assigned to one person, in any order. Output the numbers of seats in the format, described in the statement. If there are multiple possible answers, output any.
Problem Author: Alexey Kungurtsev
Problem Source: Ural School Programming Contest 2019