Longest Common Prefix

You are given a list of n strings. Your task is to find the longest common prefix among these strings. In other words, determine the longest string P that is a prefix of every string in the list. If no common prefix exists, output an empty string.

Note: The common prefix of two strings A and B is the longest string that is a prefix of both. In latex notation, if we denote the strings by \(A\) and \(B\), then the longest common prefix \(P\) satisfies \(P \preceq A\) and \(P \preceq B\), and for any other string \(Q\) with this property, \(Q \leq P\) in length.

inputFormat

The first line contains 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. If there is no common prefix, output an empty string.

3
flower
flow
flight

fl