# 重名剔除(Deduplicate)

### Description

Mr. Epicure is compiling an encyclopedia of food. He had collected a long list of candidates nominated by several belly-gods. As candidates in list are nominated by several people, duplication of name is inevitable. Mr. Epicure pay you a visit for help. He request you to remove all duplication, which is thought an easy task for you. So please hold this opportunity to be famous to all belly-gods.

### Input

1 integer in fist line to denote the length of nomination list. In following n lines, each nomination is given in each line.

### Output

All the duplicated nomination (only output once if duplication appears more multiple times), which is sorted in the order that duplication appears firstly.

### Example

Input

10
brioche
camembert
cappelletti
savarin
cheddar
cappelletti
tortellni
croissant
brioche
mapotoufu


Output

cappelletti
brioche


### Restrictions

1 < n < 6 * 10^5

All nominations are only in lowercase. No other character is included. Length of each item is not greater than 40.

Time: 2 sec

Memory: 256 MB

Hash

### 描述

Epicure先生正在编撰一本美食百科全书。为此，他已从众多的同好者那里搜集到了一份冗长的美食提名清单。既然源自多人之手，其中自然不乏重复的提名，故必须予以筛除。Epicure先生因此登门求助，并认定此事对你而言不过是“一碟小菜”，相信你不会错过在美食界扬名立万的这一良机

1 < n < 6 * 10^5

### 提示

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374 #include #include #include using namespace std; template struct node{     T data;     node * next; }; template struct list{     node * head;     int _size;     list(){         _size=0;         head=NULL;     }     void insert(T & data){         _size++;         node * ptr=new node;         ptr->data=data;         ptr->next=head;         head=ptr;     }     T & search(T & target){         node * ptr=head;         while(ptr!=NULL){             if(ptr->data==target)return ptr->data;             ptr=ptr->next;         }         return target;     } }; struct DataNode{     char name[41];     char flag;     bool operator == (const DataNode & D2){         return strcmp(this->name,D2.name)==0;     }     void operator = (const DataNode & D2){         strcpy(this->name,D2.name);         this->flag=D2.flag;     } }; int h(const char * str){     int total=0;     for(;(*str)!='\0';str++){         total+=(*str)-'a';     }     return (31*total+29)%10007; } list HashTable[10008]; int main() {     setvbuf(stdin,new char[1<<26],_IOFBF,1<<26);     setvbuf(stdout,new char[1<<26],_IOFBF,1<<26);     int n;     scanf("%d",&n);     DataNode D;     D.flag=-1;     for(int i=1;i<=n;i++){         scanf("%s",D.name);         DataNode & ptr_Data=HashTable[h(D.name)].search(D);         switch(ptr_Data.flag){             case -1:             D.flag=1;             HashTable[h(D.name)].insert(D);             D.flag=-1;             break;             case 1:             printf("%s\n",D.name);             ptr_Data.flag++;             break;         }     }     return 0; }