Longest Common Prefix

Given an array of strings, find the longest common prefix string among them. If there is no common prefix, output an empty string.

For example, if the input is ["intersperse", "internet", "interval", "intersect"], the output should be inter.

inputFormat

The input consists of multiple lines. The first line contains an integer n denoting the number of strings. Each of the following n lines contains one non-empty string.

outputFormat

Output the longest common prefix among the given strings. If there is no common prefix, output an empty string.## sample

4
intersperse
internet
interval
intersect

inter