Alien Integers

Exploratory robots are essential to expanding our understanding of the moon, Mars, and other celestial bodies. When there are two or more robots in the same vicinity, they need to be marked by humanly readable integers for purposes of visual tracking. To reduce the possibility of error in visual recognition of the robots in dark and dusty environments, numbers are chosen so that they have no digits in common. More formally, two non-negative integers are alien to each other if there is no digit which occurs in both of their decimal representations. For example, $11\, 229$ and $67\, 840$ are alien to each other, while $2\, 022$ and $427$ are not. No integer is alien to $1\, 234\, 567\, 890$.

The numbers on robots in the same area should also be close to each other numerically (for instance, to simplify processing of the marks by the software, to make them easy to remember, to distinguish them from other groups of robots marked in similar manner, …).

The Institute for Computerized Planetary Circumambulation needs a program to identify the nearest number that is alien to a given number. Can you help?


The input consists of an integer $N$ ($1 \leq N \leq 10^{15}$) given on a single line.


When there is one non-negative alien integer $Y$ closest to the input number $N$, output the value of $Y$. When there are two such integers that are equally close to the input number $N$, output both of them in ascending order, on a single line. When there is no integer alien to the input number $N$, output Impossible.

Sample Input 1 Sample Output 1
Sample Input 2 Sample Output 2
499 711
Sample Input 3 Sample Output 3
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Marko Berezovsky
Source 2021 ICPC North American Qualifier Contest (Jan 2022)
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in