Longest Common Prefix

Given a list of strings, your task is to determine the longest common prefix among them. If there is no common prefix, output an empty string. For instance, given ["flower", "flow", "flight"], the longest common prefix is fl, while for ["dog", "racecar", "car"] there is no common prefix.

The solution should read input from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The input begins with an integer n representing the number of strings. This is followed by n lines, each containing a non-empty string.

Input format example:

3
flower
flow
flight

outputFormat

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

Output format example:

fl

3
flower
flow
flight

fl