Longest Common Prefix

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

The common prefix of a set of strings is the longest initial segment that is common to all of them. For instance, if the input is flower, flow, flight, flourish, the answer will be fl because "fl" is the longest substring that is the starting segment of every string in the list. If no common prefix exists, output an empty string.

Note: The input is given through standard input and the output should be written to standard output.

inputFormat

The input starts with an integer n indicating the number of strings. This is followed by n lines, each line containing one string.

If n is 0, then the array is empty and the output should be an empty string.

outputFormat

Output a single line containing the longest common prefix of the input strings. If no common prefix exists, output an empty string.

4
flower
flow
flight
flourish

fl