Clickbait

Clickbait is something (such as a headline) designed to make readers want to click on a hyperlink especially when the link leads to content of dubious value or interest.

Rizvi works at an online news portal. His job is to clickbait people as much as possible. Unethical but the money he gets makes him forget his ethics. Greedy Rizvi!

Rizvi has a date today. So he won't be able to generate those clickbait headlines. He asked you to cover his shift and generate those headlines.

A clickbait headline consists of some words. Some of them are related to the original news and others are some trending words. Trending words always start with a '#' sign like #trending. Now the more trending words are in the headline, the better chance of people clicking the link. However if more than half of the words in the headline are trending words or there are two or more trending words adjacent to each other then people will understand that it is a clickbait and will not click the link.

Given some words, your task is to generate a headline with the highest number of words possible, using some or all words (separated by single a space) from there so that people will get clickbaited the most. If there are many possible answers with the same number of words, then print the one which is lexicographically smallest in terms of words.

A sentence will be lexicographically smaller in terms of words than another sentence with the same number of words if the first non-equal word in the first sentence is lexicographically smaller than the word in the other sentence.

Don't include '#' signs in the headlines as people will immediately understand it's a clickbait and will not click.

Input

Input starts with an integer $n$ ($0 < n \le 10^5$), number of words. The next n line contains one distinct word each. Each word consists of at most 50 lowercase Latin letters. Word starting with '#' sign means it's a trending word.

Output

In a line, print the answer. It is guaranteed that the answer contains positive number of words.

Sample

Input	Output
9 ki #wow #dekhun rizvi #zirlfriend #video shoho #korlo #picture	dekhun ki korlo rizvi picture shoho
In this testcase, The highest possible words to be added in the headline is 6. Now, there can be many ways to assemble 6 words. Such as, "wow rizvi zirlfriend shoho korlo ki" "ki korlo rizvi dekhun video shoho" "dekhun ki korlo rizvi video shoho" and many more. But the one that is lexicographically smallest in terms of words is "dekhun ki korlo rizvi picture shoho"

Inputs are big. Use faster I/O.