Longest Common Prefix

You are given a list of strings. Your task is to find the longest common prefix among them. Formally, let \( S = \{s_1, s_2, \dots, s_n\} \) be a set of strings. We define a string \( P \) to be a prefix of a string \( s \) if there exists some string \( x \) (possibly empty) such that \( s = P + x \). Find the longest string \( P \) that is a prefix of every string in \( S \). If there is no common prefix, output an empty string.

Note: The list of strings could be empty. In this case, the correct output is an empty string.

inputFormat

The input is given via standard input (stdin). The first line contains an integer ( n ) (with ( 0 \le n \le 1000 )), which represents the number of strings. Each of the following ( n ) lines contains a non-empty string. In case ( n = 0 ), there will be no additional lines.

outputFormat

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

3
flower
flow
flight

fl