You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

• 时间：1s
• 空间：256M

题目描述

小哈尼是个活泼可爱的学生，对数学总是抱着一丝既好奇又畏惧的心情。这天，数学课上老师讲到了分数的约分，这是一个让许多数字变得"瘦身"的神奇技巧。小哈尼听得津津有味，心里暗暗发誓要掌握好这个本领，让复杂的分数变得简单起来。

放学后，小哈尼迫不及待地拿出作业本，想要实践一下新学的约分技能。他翻到了一页，上面有一道题目："请将分数$\frac{163}{326}$，约分到最简形式。" 小哈尼心想："这还不简单，于是先将上下两位中的 $3$ 划去，又将上下两位中的 $6$ 划去，最终得出结果为 $\frac{1}{2}$。"

很明显这种约分方式是有问题的，但哈尼恰好得到了正确的答案。

现在小哈尼将 $\frac{a}{b}$ 这一分数按如上方式进行了约分，即每次可以划去分子和分母中相同的任意两个数字，需要满足最终得到的分子和分母不能包含前导零，得到了权值 $\frac{a’}{b’}$，小哈尼记得最终的结果与 $\frac{c}{d}$ 的分数权值恰好相同，小哈尼想知道 $\frac{a’}{b’}$ 有多少种可能的结果，从小到大按照 $a’$ 为关键词依次输出。

输入格式

从 frac.in 文件读入数据。

输入共一行，包含四个正整数 $a,b,c,d$​。

输出格式

输出到 frac.out 文件。

输出若干行，每行包含两个正整数 $a’,b’$ 所有结果按照 $a’$ 从小到大依次排序输出，注意最终结果不能包含前导零。

样例

163 326 1 2

1 2
163 326

871 1261 13 39

87 261

101 101 1 10

625329650586180138 615463967153146625 8904235798025734 8792342387592375

62329650586180138 61546396713146625

88888 8888 11 1

88 8

说明/提示

样例 3 解释

没有合法解，所以输出一个空文件。

数据范围

对于 $30\%$ 的数据，$1 \leq a,b,c,d \leq 1000$

对于 $60\%$ 的数据，$1 \leq a,b,c,d \leq 10^6$。

对于所有测评数据，$1 \leq a,b,c,d \leq 10^{18}$。