Longest Common Prefix

Given a set of sentences, your task is to find the longest common prefix shared among all the sentences. The longest common prefix is defined as the longest string that is a starting substring of every sentence. If there is no common prefix among the sentences, output an empty string.

For example, given the sentences:

• "the quick brown fox"
• "the quick brown dog"
• "the quick"

the longest common prefix is "the quick".

Input will be provided via standard input (stdin) and the result must be printed to standard output (stdout).

inputFormat

The first line contains an integer n representing the number of sentences. The following n lines each contain one sentence.

If n is 0, there are no sentences and the output should be an empty string.

outputFormat

Output a single line containing the longest common prefix from the provided sentences. If there is no common prefix, output an empty string.

3
the quick brown fox
the quick brown dog
the quick

the quick