Hide

Problem E
Colosseum of Fools

Deep in the caverns of a fallen kingdom, lies a sacred battleground for warriors all across the lands to test their skills. Tonight, b bugs have come to the arena to challenge the trials the Colosseum holds. To assist them in their battles, each bug wields several charms that can grant special abilities, such as improved survivability, greater attack speed, and enhanced attacks.

The keeper to the gate of the Colosseum wishes to compare the relative strengths of each of these b competitors. To start, each bug has a charm list, consisting of charms they intend to bring into the arena. Each of these charms belongs to a known set of c charms recorded in the Colosseum’s annals. Each of these c charms has a name, consisting of letters from a to z. To compile the charm list, each bug concatenates the names of the charms they hold into one string, without any other strings in between. For an example of this, see the sample test case.

One bug is said to be stronger than another if their charm list is lexicographically smaller than the other’s charm list. If two bugs have the same charm list, the one that appears earlier in the keeper’s list is stronger. Given this, can you produce a list of tonight’s competitors, in order of their strength?

Input

The first line of input contains two integers b and c (1b,c2105): the number of bugs, and the number of charms used in the Colosseum.

The next c lines each contain a string of lowercase Latin characters. The ith of these is the name of the ith charm. Charms are numbered from 1 to c.

The next b lines each contain a series of space-separated integers, representing each of the bugs’ charms. The bugs appear in the same order as they do as in the keeper’s list. The ith line begins with an integer ki (ki1). Then, ki integers follow, all of which are between 1 and c. The jth of these indicates the charm that appears in the jth position in the ith bug’s list. Bugs are numbered from 1 to b.

It is guaranteed that the total length of all charm names is at most 3105, and the total of all ki is at most 3105.

Output

Output b lines, each containing a single integer. The ith of these is the number of the ith strongest bug.

Notes

For the first sample test case, the charm lists for the three contestants are

  • quickslashspelltwisterdreamwielder

  • quickslashspelltwisterdreamshield

  • shamanstonedreamwielder

It can be seen from this that the order in the sample output is correct.

For the second sample test case, note that a bug may use multiple copies of a charm, and the charm’s names may not be in any known language.

Note that a string P=P1P2P3 is said to be lexicographically smaller than a string Q=Q1Q2Q3 if either:

  • P is a prefix of Q, but PQ.

  • There exists some i such that Pj=Qj for all j<i, and Pi<Qi. Here, characters are ordered alphabetically, so a is the smallest, b is the second smallest, etc.

Sample Input 1 Sample Output 1
3 5
dreamwielder
shamanstone
quickslash
spelltwister
dreamshield
3 3 4 1
3 3 4 5
2 2 1
2
1
3
Sample Input 2 Sample Output 2
3 2
aa
aaa
1 1
6 1 2 1 2 1 2
2 2 2
1
3
2
Hide

Please log in to submit a solution to this problem

Log in