Longest Common Prefix

Given a list of strings, your task is to find the longest common prefix string amongst them. If there is no common prefix, return an empty string.

For example, for the input strings ["flower", "flow", "flight"], the longest common prefix is "fl", while for ["dog", "racecar", "car"] the answer is an empty string.

The problem may be formulated mathematically as follows:

Find the longest string \( p \) such that \( p \) is a prefix of every string \( s \) in the given list \( S \).

inputFormat

The input consists of multiple lines. The first line contains a single integer \( n \) representing the number of strings. The next \( n \) lines each contain a non-empty string.

outputFormat

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

## sample

3
flower
flow
flight

fl

</p>