Indian National Olympiad in Informatics

Related:

Online Programming Contest, 11-12 February 2006

IARCS home > OLYMPIAD

Basic Division

Problem 2: Nikhil's Password, (K Narayan Kumar, CMI)

Nikhil's father has set a password on his computer to prevent Nikhil from playing games. The password is a string over the alphabet {a,b,..., z}. Nikhil's father is not sure if he will remember the password, so he decides to write it down. To ensure that the password is not obvious to someone reading the paper on which he has written it down, he hides it by writing three words on the paper. The actual password is the longest subword that is common to all these three words.

For instance, suppose Nikhil's father had written down the words aabbabbaba, abbabababa and bbabbabab. Then the hidden password is abbaba, since this is the longest common subword.

Your task is to help Nikhil find the password from the given set of three words. If there is more than one longest common subword, report any one.

Input format

The input consists of four lines. The first line of the input contains three integers M, N and K. The second line contains a word with M letters, the third line contains a word with N letters and the fourth line contains a word with K letters.

Output format

A single line containing the longest common subword among the three input words. If there is more than one longest common subword, report any one.

Test data

You may assume that N,M,K ≤ 300 in 80% of the inputs. In all inputs, N,M,K ≤ 2000.

Example

We now illustrate the input and output formats using the above example.

Sample input

10 10 9
aabbabbaba
abbabababa
bbabbabab

Sample output

abbaba