Longest Common Contiguous Substring

You are given a list of strings consisting of lowercase English letters. Your task is to find the longest contiguous substring that is common to all the strings.

If there is more than one substring that has the maximum length, output the lexicographically smallest one. If no such substring exists, output an empty string.

Note: A contiguous substring is a sequence of characters that appear consecutively in a string. For example, the substrings of abc include a, ab, abc, b, bc, and c.

The problem can be formally described as follows:

Given a list of strings \(S = [s_1, s_2, \ldots, s_n]\), find the string \(X\) such that:

\[ X = \arg\max_{x \in \bigcap_{i=1}^{n} \text{sub}(s_i)} \left( |x|, -x \right), \]

where \(\text{sub}(s)\) denotes the set of all contiguous substrings of \(s\), \(|x|\) is the length of \(x\), and \(-x\) indicates that when lengths are equal, the lexicographically smallest one is chosen.

inputFormat

The input is given from standard input (stdin) and has the following format:

N
s1
s2
...
sN

Where:

• N is an integer representing the number of strings.
• s1, s2, ..., sN are the strings consisting of lowercase English letters.

outputFormat

Output to standard output (stdout) a single line containing the longest common contiguous substring. If there is no common substring, output an empty line.

## sample

3
flower
flowing
flight

fl