Longest Common Prefix

Given a list of strings, your task is to compute the longest common prefix among all the strings. If there is no common prefix, output an empty string.

Definition: The longest common prefix of a set of strings is the longest string that is a prefix of every string in the set. For example, for the strings "flower", "flow", and "flight", the longest common prefix is "fl". If the set is empty or there is no common prefix, the answer should be an empty string.

Note: Consider the definition in mathematical notation as: Given strings \( s_1, s_2, \dots, s_n \), find the maximum length \( L \) such that \( s_1[0:L] = s_2[0:L] = \dots = s_n[0:L] \).

inputFormat

The input is read from stdin and is formatted as follows:

n
s1
s2
...
sn

Where n is an integer representing the number of strings, and each of the next n lines contains a single non-empty string. Note that the string can be empty as well.

outputFormat

Output the longest common prefix among the given strings to stdout.

## sample

3
flower
flow
flight

fl

</p>