Background

If I say I will not stop until I kiss you
Who can force me to settle
——Li Ronghao, "Bu Jiang Jiu"

In life, you cannot just “settle”. Whether you have made the best choice depends on each person.

Problem Description

You need to find an $n$-digit number $x$ that satisfies the following two conditions:

• 1. The remainder of (the sum of digits of $x$) divided by $p$ is as small as possible.
• 2. After condition 1 is satisfied, the value of $x$ is as small as possible.

Sum of digits: the total obtained by adding the digits in every position of a number. For example, the sum of digits of $123$ is $1+2+3=6$.

Input Format

The input consists of one line with two integers $n, p$.

Output Format

Output one integer, representing the answer to the problem above.

3 8

107

1 1

1

5 3

10002

2 7

16

Hint

Sample Explanation #1

Three-digit numbers include $100,101,\dots,999$. Among them, the sum of digits of $107$ is $1+0+7=8$, and the remainder of $8$ divided by $8$ is $0$.

Constraints

For $30\%$ of the testdata, $1 \le n \le 18$, $1 \le p \le 200$；
For $100\%$ of the testdata, $1 \le n \le 10^6$, $1 \le p \le 10^9$。

Translated by ChatGPT 5