Hide

Problem BE
Dominant Strings

Given two strings $s_{1}$ and $s_{2}$, we say that $s_{1}$ dominates $s_{2}$ if the (multi)set of characters in $s_{1}$ is a proper superset of the (multi)set of characters in $s_{2}$. For instance, “acmicpc” dominates “camp”, but it does not dominate “chimp” or “macpac”. For a set $S$ of strings, we call the strings in $S$ which are not dominated by any string in $S$ the dominant strings of $S$ (even if they do not dominate any strings in S).

Now, your task is simply to find all the dominant strings of a set of strings.

Input

The input contains a single set of strings, with one string per line. Each string consists of at least one and at most ten lower-case alphabetic characters (a-z). There is at least one and at most $15\, 000$ strings, and no two strings will be identical. Input is terminated by end-of-file.

Output

Output consists of all dominant strings in the input set, in alphabetical order, one word per line.

Sample Input 1 Sample Output 1
acmicpc
cccp
macpac
chimp
camp
acmicpc
chimp
macpac

Please log in to submit a solution to this problem

Log in