Longest Common Prefix

Given an array of strings, find the longest common prefix (LCP) among all strings.

The prefix is defined as the substring that appears at the beginning of all the strings in the array. If there is no common prefix, output an empty string.

For example, for the input array ["flower", "flow", "flight"], the common prefix is fl.

inputFormat

The input is given via standard input and is formatted as follows:

• The first line contains an integer n, representing the number of strings.
• The next n lines each contain one string.

outputFormat

Output the longest common prefix string using standard output. If there is no common prefix, print an empty string.

3
flower
flow
flight

fl