Longest Common Prefix

You are given a list of n strings. The task is to find the longest common prefix (LCP) among these strings. Formally, if we denote the list of strings by \(S = [s_1, s_2, \dots, s_n]\), you are to determine the longest string \(P\) such that each \(s_i\) starts with \(P\). If there is no common prefix, output an empty string.

Input Constraints: \(0 \leq n \leq 10^5\) and the sum of lengths of all strings is at most \(10^6\).

Example:

Input:
3
flower
flow
flight
Output:
fl

</p>

Use efficient methods to avoid excessive comparisons. The well-known approach involves comparing the lexicographically minimum and maximum strings in the list to derive the longest common prefix.

inputFormat

The first line contains an integer n, representing the number of strings. Each of the next n lines contains a non-empty string. In the event that n is 0, no strings are provided and the output should be an empty string.

outputFormat

Output a single line containing the longest common prefix among the given strings. If there is no common prefix, output an empty string.

## sample

3
flower
flow
flight

fl