Farmer John's Missing Cows

Farmer John collects cows with various adjectives. However, he has a short list of missing cows. Each missing cow is described by a series of adjectives. For example, consider the following list:

Farmer John has no large brown noisy cow.
Farmer John has no small white silent cow.
Farmer John has no large spotted noisy cow.

In each line, the adjectives appear in the same order. For instance, in the sample above there are 3 adjectives per line. The possible adjectives for each position can be deduced from the missing list. In the example, the first adjective can be either large or small; the second can be brown, white or spotted; and the third can be noisy or silent. This yields a total of \(2\times3\times2=12\) possible combinations. Farmer John owns a cow for every combination except those on his missing list.

If we list all the cows Farmer John owns in lexicographical (alphabetical) order (comparing adjective by adjective), determine which cow is the \(K^\text{th}\) in this order.

Partial Credit: In some cases, each adjective will have exactly two options and in others the number of options may vary between 1 and \(N\) (the number of missing cows). It is guaranteed that Farmer John owns at most \(10^9\) cows.

Note on Lexicographical Order: The order is determined by comparing adjectives in order. For example, if we have two cows described by "large brown silent" and "large spotted silent", the cow with "brown" as the second adjective comes before the one with "spotted".

inputFormat

The input begins with a line containing two integers \(N\) and \(K\) where \(1 \leq N \leq 100\) and \(K\geq 1\). \(N\) indicates the number of missing cow descriptions, and \(K\) specifies which cow (in lexicographical order) Farmer John owns that we are to determine.

Each of the following \(N\) lines contains a missing cow description in the following format:

Farmer John has no [adjective1] [adjective2] ... [adjectiveM] cow.

Each line will contain the same number \(M\) of adjectives, where \(2 \leq M \leq 30\). The possible values for each adjective can be deduced from the missing list.

outputFormat

Output the description of the \(K^\text{th}\) cow that Farmer John owns (i.e. the \(K^\text{th}\) valid adjective combination when all possible combinations are sorted in lexicographical order). The output should list the adjectives separated by a single space.

sample

3 1
Farmer John has no large brown noisy cow.
Farmer John has no small white silent cow.
Farmer John has no large spotted noisy cow.

large brown silent