Longest Common Prefix

You are given a list of strings consisting of lowercase letters. Your task is to find the longest common prefix (LCP) amongst all the given strings. If there is no common prefix, output an empty string.

Note: The input starts with an integer n representing the number of strings, followed by n strings (one per line). All strings consist of lowercase letters. It is not necessary that the strings have the same length.

The answer should be computed by comparing the strings character by character until a mismatch is found.

Examples:

• For input: 5\nabc\nabd\nabe\nabf\nabg, the output is ab.
• For input: 4\nabcdeq\nabcdef\nabcdel\nabcdef, the output is abcde.
• For input: 3\nabcd\nbcda\ncdab, the output is an empty string.

inputFormat

The first line contains an integer n, the number of strings. Each of the following n lines contains a string made up of lowercase letters.

outputFormat

Output a single line containing the longest common prefix of the input strings. If there is no common prefix, output an empty string.

5
abc
abd
abe
abf
abg

ab