Longest Common Prefix

Given a list of strings, find the longest common prefix among all the strings.

All strings consist of lowercase Latin letters and each string's length is between 1 and 200. If there is no common prefix among the strings, output an empty string.

Note: The solution should run with an expected time complexity of $O(n \times m)$, where $n$ is the number of strings and $m$ is the length of the shortest string.

inputFormat

The input is given from standard input (stdin) in the following format:

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

outputFormat

Output the longest common prefix among the given strings to standard output (stdout). If there is no common prefix, output an empty string.

3
flower
flow
flight

fl