2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Find a Number

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given two positive integers $$$d$$$ and $$$s$$$. Find minimal positive integer $$$n$$$ which is divisible by $$$d$$$ and has sum of digits equal to $$$s$$$.

Input

The first line contains two positive integers $$$d$$$ and $$$s$$$ ($$$1 \le d \le 500, 1 \le s \le 5000$$$) separated by space.

Output

Print the required number or -1 if it doesn't exist.

Examples

Input

13 50

Output

699998

Input

61 2

Output

1000000000000000000000000000001

Input

15 50

Output

-1

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/25/2022 23:02:08 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|