Longest Common Prefix

The problem asks you to find the longest common prefix string amongst an array of strings.

Given an array of strings, write a program that finds the longest common prefix. If there is no common prefix, return an empty string.

For example, given the input strings flower, flow, and flight, the longest common prefix is fl. In another case, for the inputs dog, racecar, and car, there is no common prefix, so the output should be an empty string.

Note: The solution should read the input from standard input (stdin) and produce the output to standard output (stdout).

The approach typically involves comparing characters at the same position of each string. One efficient method is to iterate through the characters of the shortest string, and for each character, check if all other strings have the same character at that position.

You may express any formulas using LaTeX formatting. For example, the length of the shortest string, denoted by $L$, is defined by $L=\min_{i}\{|s_i|\}$.

inputFormat

The first line contains an integer $n$, representing the number of strings. This is followed by $n$ lines, each containing a non-empty string.

Example:

3
flower
flow
flight

outputFormat

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

## sample

3
flower
flow
flight

fl