UT Invitational Programming Contest Fall 2019

Start

2019-11-23 19:00 UTC

UT Invitational Programming Contest Fall 2019

End

2019-11-24 00:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -190 days 0:02:41

Time elapsed

5:00:00

Time remaining

0:00:00

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!