ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Regional School Programming Contest 2019

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Victoria!

Time limit: 0.5 second
Memory limit: 256 MB
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.

Input

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.

Output

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.

Samples

inputoutput
2 2
.**|_|**.
**.|_|***
POBEDA
1A
2C
2 3
...|_|***
***|_|***
PORAZHENIE
Problem Author: Alexey Kungurtsev
To submit the solution for this problem go to the Problem set: 2143. Victoria!