What makes 2022 special?

The date of the New Year contest is January 15, 2022. Junggyeom was happy that the contest was being held, and while staring at the title he noticed that 2022 is special in some way.

Yes. When $2022$ is written in base $5$, it is $31042_{(5)}$, and each base-$5$ digit $0$, $1$, $2$, $3$, $4$ appears exactly once. The next year with this property is 2054.

You are given a number $N$ and a base $d$. Find the smallest number greater than $N$ such that, when written in base $d$, each base-$d$ digit appears exactly once. Do not write leading zeros.

The first line contains the number $N$ and the base $d$, separated by a space, both written in base $10$.

On the first line, print the smallest number greater than $N$ that, when written in base $d$, contains each base-$d$ digit exactly once. Print it in base $10$.

If no such number exists, print $-1$ on the first line.

• $1 \le N \le 10^9$
• $2 \le d \le 9$
• All input numbers are integers written in base $10$.

• A positive integer $A$ written in base $d$ as $a_n a_{n-1} \cdots a_1 a_0{}_{(d)}$ means $A = a_n \times d^n + a_{n-1} \times d^{n-1} + \cdots + a_1 \times d^1 + a_0 \times d^0$, where $a_n \neq 0$.
  • For example, $2022 = 3 \times 5^4 + 1 \times 5^3 + 0 \times 5^2 + 4 \times 5^1 + 2 \times 5^0 = 31042_{(5)}$.
• Base-$d$ digits are integers from $0$ up to but not including $d$.
• The base-$d$ representation of $A$ has each digit $0, 1, \cdots, d-1$ exactly once when $0, 1, \cdots, d-1$ each appear exactly once among $a_n, a_{n-1}, \cdots, a_0$.