Longest Common Prefix

Given an array of strings, find the longest common prefix among them. If there is no common prefix, return an empty string.

For example, given the words flower, flow and flight, the longest common prefix is fl.

The problem can be formally stated as follows:

Given a sequence of strings \(S = \{s_1, s_2, \dots, s_n\}\), determine the longest string \(P\) such that \(\forall i,\ s_i\) starts with \(P\). If no such non-empty \(P\) exists, output an empty string.

The expected time complexity is approximately \(O(n \times m)\), where \(n\) is the number of strings and \(m\) is the length of the common prefix.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

• The first line contains an integer n representing the number of words.
• The following n lines each contain a single word.

Note: If n is 0, the output should be an empty string.

outputFormat

The output, written to standard output (stdout), is a single line containing the longest common prefix among the given words. If there is no common prefix, output an empty string.

## sample

3
flower
flow
flight

fl