寻找缺失的分子

题目描述

已知等式 $a/b+(x/m)÷(c/d)=n$。在闭区间 $[left,right]$ 中寻找最小正整数 $x$ 使等式成立。

输入格式

输入一行，依次包含八个整数 $a$、$b$、$m$、$c$、$d$、$n$、$left$、$right$，其中 $b,m,c,d>0$，$left≤right$。

输出格式

若存在，第一行输出最小的 $x$，第二行输出 $x/m$ 的最简结果；若不存在，输出 NONE。

样例

输入

1 2 12 2 3 1 1 20

输出

4
1 3