DSA Homework 4

De la WikiLabs

Word Count

Little John is learning Mandarin. In order to help him look for words in a dictionary, he needs to make a list of all the new words he's encountering as he's reading a book, but he only needs each word once.

Help Little John make a list of all the different words in the book.

Requirement

Given a number of words N and a list of N words, output the number K of different words, and the list of those words, in alphabetical order. Words are considered identical only if their letter case matches.

Input Data

A file called word_count.in, containing the number of words N on the first line and N subsequent words, one word per line.

Output Data

A file called word_count.out, containing the number of different words, K on the first line, then K subsequent words, alphabetically ordered, one word per line.

Restrictions

1 ≤ N ≤ 1000000

Time complexity: O(n log n)

Examples

Input Output
8
Mircea
a
mancat
cartofi
si
piure
de
cartofi
7
Mircea
a
cartofi
de
mancat
piure
si