As you might know, a perfect squad consists of a warrior, a mage, a cleric, and a rogue. Sometimes you have to settle for less: a warrior, a mage, and a cleric can form a three-person squad, but that’s not perfect. You could form a squad consisting of a single warrior if there’s no better option.
Your guild has n members. Each guild member has a set of qualifications: they might be a warrior, a mage, a cleric, and/or a rogue. More specifically, a person can have any non-empty set of qualifications, in other words, they can have any set of one, two, three, or four qualifications.
To form a squad, you need to assemble up to four people and assign a role to everybody. Each role can be assigned to at most one person, and a person cannot have two roles, even if they have several qualifications. In this way the squad will have at most one person with the role of a warrior, at most one person with the role of a mage, and so on. The amount of distributed roles is always equal to the number of people in the squad.
You are to assemble one squad of the largest size, and if it’s not perfect you also need to put up a job ad about your guild. To make the ad, you need to determine all such qualifications that hiring one person with only one qualification would increase the maximum size of the squad.
Input
The first line contains a single integer n — the number of people in the guild (1 ≤ n ≤ 15).
Each of the next n lines contains between 1 and 4 capital letters W
(Warrior), M
(Mage), C
(Cleric), R
(Rogue), not separated by spaces, denoting the set of qualifications of a single person. The letters are given in that exact order, in other words, each of these lines can be obtained from the line WMCR
by deleting up to three letters.
Output
In the first line, write a single integer — the maximal size of a squad you can assemble.
If the maximal size is less than 4, output one more line, starting with “Looking for
” and followed by space-separated qualifications in the ad. Each qualification is one of four words: “warrior
”, “mage
”, “cleric
” or “rogue
”, in that exact order. You only need to use such qualifications that hiring one person with only one of those qualifications would increase the maximum size of the squad.
Samples
input | output |
---|
1
W | 1
Looking for mage cleric rogue |
2
M
CR | 2
Looking for warrior cleric rogue |
4
WMCR
WMCR
WMCR
WMCR | 4 |
1
WMCR | 1
Looking for warrior mage cleric rogue |
Problem Author: Valentin Zuev
Problem Source: Ural School Programming Contest 2020