DOMINST - Dominant Strings

no tags 

Given two strings s1 and s2, we say that s1 dominates s2 if the (multi)set of characters in s1 is a proper superset of the (multi)set of characters in s2. 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. There will be at most 15000 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.

Example

Input:
acmicpc
cccp
macpac
chimp
camp

Output:
acmicpc
chimp
macpac

hide comments
Medo: 2017-06-16 19:59:23

SPOILER:
Time limit should be more strict. I just passed with direct bruteforce.

mechanic: 2017-03-13 16:17:26

I solved it using bruteforce. Can anybody tell me how to solve this using hashing?

(Tjandra Satria Gunawan)(曾毅昆): 2012-12-21 16:01:45

TLE!
Finally AC! :-D
First solver using C language ;-)
1.02s is my best, my algo still slower than legrand...

Last edit: 2012-12-21 16:53:35
legrand: 2012-06-01 14:21:39

nice problem, time limit should be shorter.

Kashyap Krishnakumar: 2012-05-24 12:56:58

A nice optimization problem! :)

Buda IM (retired): 2012-05-16 08:28:04

this would be fine problem, if TL was stricter


Added by:Coach UTN FRSF
Date:2012-05-13
Time limit:4.241s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:http://uva.onlinejudge.org/external/107/10745.html