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?


The first line of input contains two integers $b$ and $c$ ($1 \leq b, c \leq 2 \cdot 10^5$): 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 $i$th of these is the name of the $i$th 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 $i$th line begins with an integer $k_ i$ ($k_ i \geq 1$). Then, $k_ i$ integers follow, all of which are between $1$ and $c$. The $j$th of these indicates the charm that appears in the $j$th position in the $i$th bug’s list. Bugs are numbered from $1$ to $b$.

It is guaranteed that the total length of all charm names is at most $3 \cdot 10^5$, and the total of all $k_ i$ is at most $3 \cdot 10^5$.


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


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 = P_1P_2P_3\dots $ is said to be lexicographically smaller than a string $Q = Q_1Q_2Q_3\dots $ if either:

  • $P$ is a prefix of $Q$, but $P \neq Q$.

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

Sample Input 1 Sample Output 1
3 5
3 3 4 1
3 3 4 5
2 2 1
Sample Input 2 Sample Output 2
3 2
1 1
6 1 2 1 2 1 2
2 2 2
CPU Time limit 2 seconds
Memory limit 1024 MB
Statistics Show
Dan Alden Baterisna
Source NUS Competitive Programming
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in