Problem E
Con-cat-nation
In Catopolis, there is a widely held belief that the neighboring nation Pupridge is preparing to invade. The coolest cats have decided to send their best concats into Pupridge as spies, but there’s a problem. Pupridge has a bullet-proof identification scheme: every pet seeking entry must present an identifier in the form of a string consisting only of lower-case letters “a” to “z”. The Border Collies check two things: that the identifier’s length is within certain allowed bounds, and that every character in the identifier is followed by an allowed successor character.
More specifically, the Border Collies have decided on a minimum allowed identifier length $x$, a maximum allowed identifier length $y$, and, for each lower-case letter $c$, a list of letters that are allowed to follow $c$. Characters at the end of identifiers are not checked for valid successors. For example, if the only character allowed to follow “a” is “a”, then “aaaaa” is a valid identifier, while “az” is not, as “z” is not allowed to follow “a”.
Cats cannot type, so they cannot forge identifiers!
Of course, the crafty cats have found a workaround: they can use a scanner and printer to append identifiers of fellow cats to their own identifiers! Resources are scarce, so each cat can only append one other identifier to their own, and this identifier has to be from the pool of existing cat identifiers (note that cats are allowed to append a copy of their own identifier).
For each cat, it is your job to figure out if they can pass verification under this scheme!
Input
The first line contains space-separated integers $N$ ($1 \leq N \leq 10^5$), $x$, $y$ ($0 \leq x \leq y \leq 20$): the number of cats, the minimum allowed length of the identifier, and the maximum allowed length of the identifier. $26$ lines follow, denoting the valid successors of the characters “a, b, c, …, z”, respectively. Each line has the format $k$ $S$, where $k$ is the number of valid successors the character has and $S$ is a string of length $k$ containing all of the valid successors. Finally, $N$ lines follow, each containing a string $id_ i$ ($1 \leq |id_ i| \leq 20$), giving the identifier of the $i$th cat.
Output
For each cat, output “Feline good!” if the cat can pass verification and “ Get meowt!” if they cannot. The output should follow the order given in the input, and each cat’s output should be on a new line.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 10 20 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz paws catnip purrfect |
Feline good! Feline good! Feline good! |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 10 20 1 a 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxyz zzzzza dogs |
Get meowt! Feline good! |
