Longest Common Prefix

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

The input will be read from standard input (stdin) and the result should be written to standard output (stdout). The first line of input consists of an integer N, representing the number of strings. The following N lines each contain one string. The output is a single line containing the longest common prefix. If there is no common prefix, output an empty line.

The longest common prefix is defined as the longest string P such that every string in the array starts with P. Formally, if the output is P, then for each string S in the input array, the equation S = P + X for some string X (possibly empty) holds.

The formula for the comparison in LaTeX is:

$$\text{if } S_i[0:len(P)] = P \quad \forall i, \text{ then } P \text{ is a common prefix.}$$

inputFormat

The first line contains an integer N (1 ≤ N ≤ 10⁴), the number of strings.

Each of the following N lines contains a non-empty string. The total length of all strings does not exceed 10⁵.

outputFormat

Output a single string representing the longest common prefix among the given strings. If there is no common prefix, output an empty line.

## sample

3
flower
flow
flight

fl