Longest Common Prefix

Given a list of strings, your task is to find the longest common prefix ( \(L\)) that is shared among all the strings. If there is no common prefix, output an empty string.

For example, given the strings "flower", "flow", and "flight", the longest common prefix is "fl". Use the following steps:

1. Read an integer \(n\) which represents the number of strings.
2. Then, read \(n\) strings (one per line).
3. Find the longest string \(L\) that is a prefix to every given string. If such a prefix does not exist, output an empty string.

Note: A prefix is a substring that starts at the beginning of a string. The solution should handle edge cases such as when the list is empty, when all strings are empty, or when there is only one string in the input.

inputFormat

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

n
s1
s2
...
sn

Here, \(n\) is an integer representing the number of strings, and each \(s_i\) is a non-empty string. Note that strings do not contain spaces.

outputFormat

Output the longest common prefix string via standard output (stdout). If there is no common prefix, output an empty string.

3
flower
flow
flight

fl