As part of the global effort to combat COVID-19, scientists are sequencing the genome of many samples that they find. Using this information, it is possible to trace how the virus evolves and how it spread, as well as helps in finding a cure.
As a simple model, the virus's genome can be represented by a string consisting of the letters
G. The difference between two strains and is equal to the number of positions in which their genomes differ. A strain of the virus is to be an ancestor of and if both the difference between and and the difference between and is strictly smaller than the difference between and .
Given three sequences, determine if one of them is an ancestor of the other two.
The input begins contains three strings , the three sequences. All three strings are the same length of less than or equal to characters.
Output one of the strings if it is an ancestor of the other two; or
Sample Input 1
ACTG CCTG CCTA
Sample Output 1
Sample Input 2
ACTG ATCG CTTG
Sample Output 2