寻找缺失的分子

题目描述

给定分数 $a/b$、目标分数 $c/d$ 和分母 $m$。在闭区间 $[left,right]$ 中寻找最小正整数 $x$，使 $a/b+x/m=c/d$。

输入格式

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

输出格式

如果存在，第一行输出最小的 $x$，第二行输出补上的分数 $x/m$ 的分子和分母；如果不存在，输出 NONE。

样例

输入

1 3 12 3 4 1 10

输出

5
5 12