Under construction

Still being built. Things may change

Anagram

Interview

Time limit4sMemory limit256 MB

Summary
Given a list of lowercase words, print each word whose anagram has not appeared earlier in the list, keeping the input order.
Level

Easy3 of 10

Topics
Hash map, String, Sorting
Solved
No attempts yet

Statement

Two words are anagrams if the letters of the first word can be reordered to obtain the second one. An instance of anagrams is the pair "listen" and "silent".

Task

You are given a list of words, each word consisting of lowercase letters. Your goal is to filter this list by dropping any word whose anagram has already appeared earlier on the list.

Input

The first line contains nn, the length of the list. This is followed by nn lines, each containing one word.

Output

Print out the list of words without anagrams, one word per line. The words should appear in the same order as given in the input.

Constraints

  • 1≤n≤1051 \le n \le 10^5
  • All letters are lowercase letters of the English alphabet.
  • Length of any word will not exceed 100100.

Examples1

  1. Example 1

    Input
    5
    listen
    santa
    satan
    silent
    cat
    
    Expected output
    listen
    santa
    cat