자릿수 바꾸기

도비다스(Dovydas)가 유스타스(Justas)에게 두 자연수 $N$과 $M$을 알려 주었다. 유스타스가 할 일은 $N$을 될 수 있는 대로 큰 수로 만드는 것이다. 그는 $N$의 자릿수를 한 번에 하나씩 바꿀 수 있는데, 자릿수를 한 번 바꿀 때마다 그 수를 $M$으로 나눈 나머지가 반드시 더 커져야 한다. 자릿수를 바꿀 때 맨 앞자리를 $0$으로 바꾸는 것은 허용되지 않는다.

예를 들어 $N = 1399$, $M = 11$이면 처음에 $N$을 $M$으로 나눈 나머지는 $1399 \bmod 11 = 2$이다. 유스타스가 첫 번째로 $N$의 마지막 자릿수를 바꾼다면, 나머지를 크게 만드는 값들, 즉 $0, 1, \dots, 6$ 중에서 고를 수 있다.

그가 $3$을 골랐다고 하자. 이제 $N$은 $1393$이다. 여기서 유스타스가 맨 앞자리를 바꾼다면 가능한 값은 $9$뿐이다(맨 앞자리를 $0$으로 바꿀 수 없음에 유의하라).

$9393$은 더 이상 바꿀 수 없다. 이미 $11$로 나눈 나머지가 가능한 최댓값에 도달했기 때문이다($9393 \bmod 11 = 10$). 이것이 유스타스의 결과가 된다.

그러나 이것이 가능한 최선의 결과는 아니다. 가장 좋은 결과는 $9899$이며, 예를 들어 다음과 같은 단계로 도달할 수 있다.

유스타스가 도달할 수 있는 가장 큰 수를 구하여라.

한 줄에 두 정수 $N$과 $M$이 주어진다.

유스타스가 도달할 수 있는 가장 큰 수를 출력한다.

• $1 \le N < 10^{17}$
• $1 \le M \le 10^9$