Description

Runaround numbers are positive integers that contain no $0$ and have no repeated digits (for example, $81362$). They must also have the following property:

Starting from the leftmost digit (in $\color{red}{8}\color{black}1362$, that digit is $8$), move to the right a number of positions equal to the value of the current digit (wrapping around to the leftmost digit after the rightmost one; in $\color{red}{8}\color{black}1362$, you move $8$ steps). You will land on another new digit (in $\color{red}{8}\color{black}1362$, this is $\color{red}8\color{black}\to 1\to 3\to 6\to 2\to 8\to 1\to 3\to \color{red}6$; if you land on a digit that has already been visited, then the number is not a runaround number).

Repeat this process. If you return to the leftmost digit after visiting every digit exactly once, then the integer is a runaround number.

Using $81362$ as an example, the following simulation shows that $81362$ is a runaround number:

$$\color{red}8\color{black}\to 1\to 3\to 6\to 2\to 8\to 1\to 3\to \color{red}6$$$$\color{red}6\color{black}\to 2\to 8\to 1\to 3\to 6\to \color{red}2$$$$\color{red}2\color{black}\to 8\to \color{red}1$$ $$\color{red}1\color{black}\to \color{red}3$$ $$\color{red}3\color{black}\to 6\to 2\to \color{red}8$$

Task: Given a positive integer $m$, find the smallest runaround number $m'$ that is greater than $m$.

It is guaranteed that $m' \le 2^{32} - 1$.

Input Format

A single line containing $m$.

Output Format

A single line containing the smallest runaround number $m'$ such that $m' > m$.

81361

81362

Hint

Constraints: For $100\%$ of the testdata, $1 \le m \le 10^9$.

Source: USACO 2.2.

Translated by ChatGPT 5