Given three strings consisting of lowercase Latin letters. With these strings, you can perform the following operations: either replace one character of the string with two of the same characters (for example, replace the character "a" with "aa"), or, conversely, replace two consecutive identical characters with one of the same character.
It is necessary to use these operations to make all three strings equal to some other common string S, or to determine that it is impossible to do so. At the same time, it is necessary to minimize the total number of operations.
Input
The program receives as input three strings consisting of lowercase Latin letters. The length of each line does not exceed 100 characters.
Imprint
If it is possible to make all three strings equal using the indicated operations, print a string S such that the total number of operations required to convert all three given strings to the string S will be minimal. If this cannot be done, the program should print a single word IMPOSSIBLE (in capital letters).
Examples
| # |
Input |
Output |
| 1 |
aaaza
aazzaa
azzza |
aazza |
| 2 |
xy
yx |
IMPOSSIBLE |