Longest Common Prefix

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

Formally, let (S = [s_1, s_2, \dots, s_n]) be the list of strings. You need to find the largest string (P) such that for every (s_i \in S), (P) is a prefix of (s_i) (i.e., (s_i = P + \text{remaining})). If no such non-empty (P) exists, output an empty string.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (n) that represents the number of strings. The following (n) lines each contain one string.

outputFormat

Output a single line to standard output (stdout) containing the longest common prefix among the provided strings. If there is no common prefix, output an empty string.## sample

3
flower
flow
flight

fl