Longest Common Prefix

You are given a list of strings. Your task is to find the longest common prefix string among these strings.

If there is no common prefix, output an empty string.

Note: The common prefix is the initial part of the string that is shared by all the strings in the list.

For example, if the input strings are flower, flow, and flight, the longest common prefix is fl.

Input/Output Instructions: Your solution should read from stdin and output the answer to stdout.

inputFormat

The input starts with an integer N representing the number of strings. The following N lines each contain one string.

outputFormat

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

3
flower
flow
flight

fl