Longest Common Prefix

Given a list of strings, your task is to find the longest common prefix among all the strings.

The common prefix of a set of strings is the longest initial segment (i.e. beginning part) that is shared by all the strings. If there is no common prefix, output an empty string.

Note:

• If the list is empty, the output should be an empty string.
• All strings consist of lowercase English letters.

Mathematically, if the list is given as \( S = [s_1, s_2, \dots, s_n] \), you are to find the largest string \( P \) such that \( P \) is a prefix of every \( s_i \) for \( i=1,2,\dots,n\). If no such \( P \) exists (except the empty string), output "".

For example:

• For \( S = [\texttt{flower}, \texttt{flow}, \texttt{flight}] \), the longest common prefix is \( \texttt{fl} \).
• For \( S = [\texttt{dog}, \texttt{racecar}, \texttt{car}] \), there is no common prefix and the output is an empty string.

inputFormat

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

1. An integer \( n \) representing the number of strings.
2. Followed by \( n \) lines, each containing a single string.

For example:

3
flower
flow
flight

outputFormat

Output the longest common prefix to standard output (stdout). If there is no common prefix, output an empty string.

For the sample input above, the output should be:

fl

## sample

3
flower
flow
flight

fl