Longest Common Prefix

You are given a list of words. Your task is to find the longest common prefix string amongst these words. If there is no common prefix, output an empty string.

The input is read from stdin and the result should be printed to stdout.

The first line of input contains a single integer \(n\) denoting the number of words. Each of the following \(n\) lines contains one word.

inputFormat

The input begins with an integer \(n\) (\(0 \le n \le 10^5\)), which represents the number of words. The following \(n\) lines each contain a non-empty string consisting of lowercase English letters. It is guaranteed that the total length of all words does not exceed \(10^6\).

outputFormat

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

3
flower
flow
flight

fl