Longest Common Prefix

You are given a list of n words. Your task is to find the longest common prefix string shared among all the words. If there is no common prefix, output an empty string.

More formally, let \(words = [w_1, w_2, \dots, w_n]\). Find the longest string \(P\) such that \(P\) is a prefix of every \(w_i\) in \(words\). If no such \(P\) exists (i.e. \(w_1, w_2, \dots, w_n\) do not share any common prefix), output the empty string.

Note: A prefix of a string is a substring that starts at the beginning of the string. For example, the prefixes of "flight" are "f", "fl", "fli", "flig", "fligh", and "flight".

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains a single integer n representing the number of words.
• Each of the next n lines contains one word.

It is guaranteed that n is at least 1.

outputFormat

Output the longest common prefix string to standard output (stdout). If no common prefix exists, output an empty string.

4
flower
flow
flight
flog

fl