Longest Common Prefix

Given a list of strings, your task is to find the longest common prefix amongst all the strings. The longest common prefix is defined as the longest string that is a beginning substring of every string in the list.

For instance, if the list is ["flower", "flow", "flight", "fluctuate"], the longest common prefix is "fl". If there is no such common prefix, output an empty string.

In mathematical terms, if we denote the common prefix as \(P\), then for each string \(s_i\) in the list, there exists an index \(k\) such that \(P = s_i[0:k]\) and \(P\) is the longest possible string with this property.

inputFormat

The input is read from stdin and is structured as follows:

1. The first line contains an integer \(n\) representing the number of strings.
2. The following \(n\) lines each contain one string.

outputFormat

Output the longest common prefix of the given list of strings to stdout. If there is no common prefix, print an empty string.

4
flower
flow
flight
fluctuate

fl