13 50

699998

61 2

1000000000000000000000000000001

15 50

-1

#include<iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

typedef long long ll;

using namespace std;

const int n=,m=;

int  p,x;

bool vis[n][m];//记录是否走过, 走过成"1"

struct node {//记录路径

    int len;//当前第几数位

    int sum;//当前数位和.

    int mod;//当前余数和,要一个一个加进去,

    //上一个的值要被下一个利用才可以得到下一个的

    node();

    char ans[];//节省空间

} head,tail;//从头到尾部,表示前一位h->t

//也可以开一个p[a][]

node::node() {

    len=-,sum=,mod=;

    memset(ans,,sizeof(ans));//初始化

}

void bfs() {

    queue<node>q;//倒序输出,队列

    q.push(head);//头部入列,

    while(!q.empty()) {//列为空,且之前没有新的tail压入queue,

        //遍历求和范围超过了x,宽搜层数达到了极限--无解

        head=q.front();//路径头部更新, 回到上一层,某层ans=ix队首压入,然后讨论

        q.pop(); //弹出这一层//也可以写在后面

        if(head.mod==&&head.sum==x) {

            cout<<head.ans<<endl;//有解

            return;

        }

        for(int i=; i<=; i++) {//遍历这一层,宽度为位数0,9

            tail=head;//路径尾部更新,回到上一层

            tail.len++;//长度更新,深度更新,第几位数

            tail.sum+=i;//和更新

            tail.mod=(tail.mod*+i)%p;//余数更新

            tail.ans[tail.len]=i+'';// 更新当前这一层/长度/位数的值--0,9都试一次,

            if(tail.sum<=x&&vis[tail.mod][tail.sum]==) {

                //如果遍历过就直接排除,不更新,

                //如果sum超过了x直接跳过,不更新路径

                //tail=head不会和之前有区别

                vis[tail.mod][tail.sum]=;//标记表示遍历过了

                q.push(tail);//更新路径队列,压入尾部,

                //表示这个位数为"i"时可以继续往下讨论,

                //用queue记住还有可能讨论的值

            }

        }

    }

    cout<<-<<endl;//如果队列最终为空,必为无解

}

int main() {

    while(cin>>p>>x) {

        memset(vis,,sizeof(vis));

        bfs();

    }

    return ;

}