ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5418: 黑客密码

内存限制：256 MB 时间限制：2 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：5 通过：5
提交提交记录统计Web Board

题目描述

Polycarpus参加了一场黑客入侵新安全信使的竞赛。他几乎赢了。


在仔细研究了交互协议之后，Polycarpus得出结论，如果他将应用程序的公钥适当地分成两部分，就可以获得密钥。公钥是一个长整数，甚至可以由一百万个数字组成！

Polycarpus需要找到这样一种方法，将公钥分成两个非空部分，即第一（左）部分可以被a整除，作为一个单独的数字，第二（右）部分可以作为一个独立的数字被b整除。这两部分都应该是没有前导零的正整数。Polycarpus知道a和b值。

帮助Polycarpus并找到任何合适的方法来剪切公钥。

Polycarpus participates in a competition for hacking into a new secure messenger. He's almost won.
Having carefully studied the interaction protocol, Polycarpus came to the conclusion that the secret key can be obtained if he properly cuts the public key of the application into two parts. The public key is a long integer which may consist of even a million digits!
Polycarpus needs to find such a way to cut the public key into two nonempty parts, that the first (left) part is divisible by a as a separate number, and the second (right) part is divisible by b as a separate number. Both parts should be positive integers that have no leading zeros. Polycarpus knows values a and b.
Help Polycarpus and find any suitable method to cut the public key.
Input
The first line of the input contains the public key of the messenger − an integer without leading zeroes, its length is in range from 1 to 106 digits. The second line contains a pair of space-separated positive integers a, b (1≤a,b≤108).
Output
In the first line print "YES" (without the quotes), if the method satisfying conditions above exists. In this case, next print two lines − the left and right parts after the cut. These two parts, being concatenated, must be exactly identical to the public key. The left part must be divisible by a, and the right part must be divisible by b. The two parts must be positive integers having no leading zeros. If there are several answers, print any of them.
If there is no answer, print in a single line "NO" (without the quotes).
Examples
Input 
116401024
97 1024
Output 
YES
11640
1024
Input 
284254589153928171911281811000
1009 1000
Output 
YES
2842545891539
28171911281811000
Input 
120
12 1
Output 
NO

输入格式

输入的第一行包含信使的公钥——一个不带前导零的整数，其长度在1到10^6位之间。第二行包含一对空格分隔的正整数a，b（1≤a，b≤10^8）。

输出格式

如果满足上述条件的方法存在，则在第一行打印“YES”（不带引号）。在这种情况下，接下来打印两行——切割后的左侧和右侧部分。连接的这两个部分必须与公钥完全相同。左边的部分必须可以被a整除，右边的部分必须被b整除。这两个部分必须是没有前导零的正整数。如果有几个答案，请打印其中任何一个。
如果没有答案，请打印一行“NO”（不带引号）

示例



Input 
116401024
97 1024
Output 
YES
11640
1024
Input 
284254589153928171911281811000
1009 1000
Output 
YES
2842545891539
28171911281811000
Input 
120
12 1
Output 
NO

输入样例 复制 

116401024
97 1024

输出样例 复制 

YES
11640
1024

分类标签