Longest Common Prefix

Given a list of strings, determine the longest common prefix among them. The longest common prefix is defined as the initial substring that is common to all strings. If there is no common prefix, output an empty string.

For instance, for the strings flower, flow, and flight, the longest common prefix is fl. In contrast, for the strings dog, racecar, and car, there is no common prefix, so the result is an empty string.

The formula for checking a prefix in LaTeX can be written as: \( \text{prefix}(s) = s[1\ldots k] \) such that for every string \( t \) in the list, \( t[1\ldots k] = s[1\ldots k] \).

inputFormat

The first line contains a single integer \( n \) (where \( 0 \leq n \leq 10^4 \)), representing the number of strings. The following \( n \) lines each contain a non-empty string, consisting of lowercase English letters.

outputFormat

Output a single line containing the longest common prefix among the \( n \) strings. If no common prefix exists, output an empty string.

3
flower
flow
flight

fl