Longest Common Prefix

Given a list of strings, your task is to find the longest common prefix string amongst them.

If there is no common prefix, output an empty string.

Consider the case where the input list might be empty, in which case you should also output an empty string.

Note: A prefix is a substring that appears at the start of a string.

The solution should be efficient enough to handle a large number of strings.

Formally, if the strings are \(s_1, s_2, \ldots, s_n\), you are to find the longest string \(p\) such that for every \(i = 1,2,\ldots,n\), the string \(s_i\) starts with \(p\). If no such \(p\) exists other than the empty string, then return the empty string.

inputFormat

The input is given via standard input (stdin) and is formatted as follows:

1. The first line contains an integer \(n\) (where \(0 \leq n \leq 10^5\)), representing the number of strings.
2. Each of the next \(n\) lines contains a single string composed of lowercase English letters.

If \(n = 0\), then there are no strings.

outputFormat

Output a single line to standard output (stdout) containing the longest common prefix shared by all \(n\) strings. If no common prefix exists, output an empty string.

## sample

3
flower
flow
flight

fl