Longest Common Subsequence in Multiple Strings

Given a list of strings, the task is to find the longest common subsequence (LCS) that appears in all the strings when converted to lowercase.

The LCS of two strings is defined by the recurrence:

$$L_{i,j} = \begin{cases} 0 & \text{if } i=0 \text{ or } j=0, \\ L_{i-1,j-1}+1 & \text{if } X[i-1] = Y[j-1] \text{ (case-insensitive)}, \\ \max\{L_{i-1,j],\, L_{i,j-1}\} & \text{otherwise}. \end{cases} $$
If there is no common subsequence, output an empty string.

inputFormat

The input is read from standard input (stdin). The first line contains an integer n which denotes the number of strings. Each of the following n lines contains one string.

outputFormat

Print a single string to standard output (stdout) representing the longest common subsequence present in all strings (in lowercase). If no common subsequence exists, print an empty string.## sample

1
abracadabra

abracadabra