Longest Common Prefix

Given an array of strings, your task is to find the longest common prefix string among them.

If there is no common prefix, output an empty string. The common prefix is defined as the longest string that is a prefix of every string in the array.

For example, given the strings flight, flow, and flower, the longest common prefix is fl. If there is an array with only one string, the common prefix is the string itself. In case of an empty list of strings, the result is an empty string.

Mathematically, if we denote the array of strings as \( S = [s_1, s_2, \dots, s_n] \), the answer is the longest string \( P \) such that \( \forall s_i \in S,\, s_i = P + x_i \) for some (possibly empty) string \( x_i \).

inputFormat

The first line of input contains a single integer \( n \) which represents the number of strings.

Then follow \( n \) lines, each containing one string. Note that a string may be empty.

outputFormat

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

3
flight
flow
flower

fl