import java.io.IOException; import java.io.InputStream; import java.util.Arrays; import java.util.NoSuchElementException; import java.util.PriorityQueue; public class Main { public static void main(String[] args) { new Main().run(); } long gcd(long a, long b) { return b==0?a:gcd(b,a%b); } class Q implements Comparable{ long n; long d; public Q(long n, long d) { long g=gcd(n,d); this.n=n/g; this.d=d/g; } @Override public int compareTo(Main.Q o) { return Long.compare(-(n*o.d-o.n*d), 0); } } final long p=(long)1e9+7; long[] inv=new long[1000000]; { inv[0]=inv[1]=1; for (int i=2;i Integer.MAX_VALUE) throw new NumberFormatException(); return (int) nl; } public double nextDouble() { return Double.parseDouble(next()); } } static void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }