Problem: You 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 ≤ d ≤ 500, 1 ≤ s ≤ 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

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String args[]) {new Main().run();}

	FastReader in = new FastReader();
	PrintWriter out = new PrintWriter(System.out);
	void run(){
		work();
		out.flush();
	}
	long mod=998244353;
	long gcd(long a,long b) {
		return b==0?a:gcd(b,a%b);
	}
	void work() {
		int d=in.nextInt();
		int s=in.nextInt();
		boolean[][] vis=new boolean[s+1][d]; 
		int[][][] route=new int[s+1][d][];
		LinkedList<int[]> queue=new LinkedList<>();
		for(int i=1;i<=9;i++) {
			if(i>s)break;
			queue.add(new int[] {i,i%d});
			route[i][i%d]=new int[]{-1,-1,i};
			vis[i][i%d]=true;
		}
		while(queue.size()>0) {
			int[] q=queue.poll();
			for(int i=0;i<=9;i++) {
				int nx=q[0]+i,ny=(q[1]*10+i)%d;
				if(nx<=s&&!vis[nx][ny]) {
					vis[nx][ny]=true;
					queue.add(new int[] {nx,ny});
					route[nx][ny]=new int[] {q[0],q[1],i};
				}
			}
		}
		if(!vis[s][0]) {
			out.println(-1);
			return;
		}
		int[] A=route[s][0];
		StringBuilder sb=new StringBuilder();
		while(true) {
			sb.append(A[2]);
			if(A[0]==-1)break;
			A=route[A[0]][A[1]];
		}
		out.println(sb.reverse().toString());
	}
}	



class FastReader
{
	BufferedReader br;
	StringTokenizer st;

	public FastReader()
	{
		br=new BufferedReader(new InputStreamReader(System.in));
	}

	public String next() 
	{
		if(st==null || !st.hasMoreElements())
		{
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	public int nextInt() 
	{
		return Integer.parseInt(next());
	}

	public long nextLong()
	{
		return Long.parseLong(next());
	}
}