Longest Common Prefix

Given an array of strings, find the longest common prefix among them. If there is no common prefix, output an empty string. The comparison is case-sensitive, and you are not allowed to use any built-in library functions specifically designed to solve the problem.

For example, for the input: ["flower", "flow", "flight"], the output should be "fl". If there is no common prefix among the strings (for example, ["dog", "racecar", "car"]), the answer is an empty string.

Note: If the array contains only one string, output that string directly.

Mathematical formulation:

Let \(S = [s_1, s_2, \ldots, s_n]\) be the array of strings. Find the maximum integer \(k\) such that \(s_1[1\ldots k] = s_2[1\ldots k] = \cdots = s_n[1\ldots k]\). If no such \(k \geq 1\) exists, output an empty string.

inputFormat

Input is read from stdin and has the following format:

N
s1
s2
...
sN

Where N is an integer representing the number of strings, and each of the following N lines contains one string.

outputFormat

The output is printed to stdout and is a single line containing the longest common prefix among the given strings. If there is no common prefix, print an empty string.

## sample

3
flower
flow
flight

fl