Inspector Craig once visited his old friend Norman McCulloch, whom he had not seen for several years. They became friends while they were students at Oxford University, and Craig always remembered those days and his friend fondly—a good-natured, if somewhat eccentric, person who was always inventing various technical curiosities. Although this story takes place before the invention of modern computers, McCulloch had already managed to construct something like a mechanical calculating device—primitive by today's standards.
This machine accepts an integer as input and, if it is valid, produces an integer according to certain well-defined rules. Here, a number refers to any positive integer, written in the usual way as a sequence of digits through .
For any number (possibly even the empty number), (here and elsewhere, denotes the concatenation of the numbers and ) is valid, and produces .
If is valid, then is also valid. If produces , then produces .
If is valid, then is also valid. If produces , then produces the reverse of (i.e., the number formed by writing the digits of in reverse order).
If is valid, then is also valid. If produces , then produces (i.e., repeated).
If is valid, then is also valid. If produces , then produces .
If is valid, then is also valid. If produces , then also produces .
If is valid, then is also valid. If produces , then produces with its last digit removed if has at least one digit, or the empty number if is empty.
Your task is to determine the number generated by McCulloch's machine for a given number .
The input consists of a single line containing the integer , consisting of no more than 10^5 digits.
Output a single line containing the number generated from by McCulloch's machine. If is not valid, output Invalid input. It is guaranteed that the length of the output does not exceed 10^6.
Example 1