Longest Shared Prefix

You are given a collection of N strings. Your task is to determine the longest common prefix among these strings. In other words, find the longest string L such that every string in the given collection starts with L.

If there is no common prefix, you should output an empty string.

For example, consider the following two cases:

• Input: ["flower", "flow", "flight"] — Output: fl
• Input: ["dog", "racecar", "car"] — Output: ""

Note: The solution should be implemented such that it reads from standard input (stdin) and writes to standard output (stdout).

inputFormat

The input is provided via stdin in the following format:

N
s1
s2
...
sN

Where N is the number of strings, and each si is a non-empty string.

outputFormat

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

## sample

3
flower
flow
flight

fl