import java.awt.Dimension; import java.awt.Point; import java.io.*; import java.math.BigInteger; import java.util.*; import java.util.function.*; class Main{ static SimpleScanner sc=new SimpleScanner(System.in); static SimpleWriter out=new SimpleWriter(System.out); public static void main(String[]args){ int H=sc.nextInt(); int W=sc.nextInt(); var A=new Matrix(H,W); for(int i=0;i0){ array[temp++]=i; } } } static void insertSort(int[] array){ insertSort(array,0,array.length); } static void insertSort(int[] array,int l,int r){ for(int i=l+1;inum){ array[j]=array[j-1]; --j; } array[j]=num; } } static void insertSort(long[] array){ insertSort(array,0,array.length); } static void insertSort(long[] array,int l,int r){ for(int i=l+1;inum){ array[j]=array[j-1]; --j; } array[j]=num; } } static void insertSort(char[] array){ insertSort(array,0,array.length); } static void insertSort(char[] array,int l,int r){ for(int i=l+1;inum){ array[j]=array[j-1]; --j; } array[j]=num; } } static > void insertSort(E[] array){ insertSort(array,0,array.length); } static > void insertSort(E[] array,int l,int r){ for(int i=l+1;i0){ array[j]=array[j-1]; --j; } array[j]=num; } } static void reverseInsertSort(int[] array){ reverseInsertSort(array,0,array.length); } static void reverseInsertSort(int[] array,int l,int r){ for(int i=l+1;i> void reverseInsertSort(E[] array){ reverseInsertSort(array,0,array.length); } static > void reverseInsertSort(E[] array,int l,int r){ for(int i=l+1;i E[][] rotateR(E[][] array,E[][] ans){ for(int i=0;iarray[k][ans.length-index-1]); } return ans; } static long[][] rotateL(long[][] array){ long[][] ans=new long[array[0].length][array.length]; for(int i=0;iarray[k][ans.length-index-1]); } return ans; } static char[][] rotateL(char[][] array){ char[][] ans=new char[array[0].length][array.length]; for(int i=0;i E[][] rotateL(E[][] array,E[][] ans){ for(int i=0;i> route){ int[] count=new int[route.size()]; int pathCount=0; for(ArrayList path: route){ for(int point: path){ ++pathCount; ++count[point]; } } ArrayDeque deq=new ArrayDeque<>(); for(int i=1;i0){ int nowP=deq.pollFirst(); for(int nextP: route.get(nowP)){ ans[index][0]=nowP; ans[index++][1]=nextP; if(--count[nextP]==0){ deq.add(nextP); } } } return ans; } static int[][] topologicalSort(int[][] route){ int[] count=new int[route.length]; int pathCount=0; for(int[] path: route){ for(int point: path){ ++pathCount; ++count[point]; } } ArrayDeque deq=new ArrayDeque<>(); for(int i=1;i0){ int nowP=deq.pollFirst(); for(int nextP: route[nowP]){ ans[index][0]=nowP; ans[index++][1]=nextP; if(--count[nextP]==0){ deq.add(nextP); } } } return ans; } static void swap(int[] array,int a,int b){ int temp=array[a]; array[a]=array[b]; array[b]=temp; } static void swap(long[] array,int a,int b){ long temp=array[a]; array[a]=array[b]; array[b]=temp; } static void swap(double[] array,int a,int b){ double temp=array[a]; array[a]=array[b]; array[b]=temp; } static void swap(char[] array,int a,int b){ char temp=array[a]; array[a]=array[b]; array[b]=temp; } static void swap(boolean[] array,int a,int b){ boolean temp=array[a]; array[a]=array[b]; array[b]=temp; } static void swap(E[] array,int a,int b){ E temp=array[a]; array[a]=array[b]; array[b]=temp; } static void swap(int[][] array,int a,int b,int c,int d){ int temp=array[a][b]; array[a][b]=array[c][d]; array[c][d]=temp; } static void swap(long[][] array,int a,int b,int c,int d){ long temp=array[a][b]; array[a][b]=array[c][d]; array[c][d]=temp; } static void swap(double[][] array,int a,int b,int c,int d){ double temp=array[a][b]; array[a][b]=array[c][d]; array[c][d]=temp; } static void swap(char[][] array,int a,int b,int c,int d){ char temp=array[a][b]; array[a][b]=array[c][d]; array[c][d]=temp; } static void swap(boolean[][] array,int a,int b,int c,int d){ boolean temp=array[a][b]; array[a][b]=array[c][d]; array[c][d]=temp; } static void swap(E[][] array,int a,int b,int c,int d){ E temp=array[a][b]; array[a][b]=array[c][d]; array[c][d]=temp; } static boolean nextPermutation(int[] array){ int index1=0; for(int i=1;i> boolean nextPermutation(E[] array){ int index1=0; for(int i=1;iarray[i]){ index1=i; } } if(--index1<0){ return false; } int index2=0; int max=Integer.MIN_VALUE; for(int i=index1+1;iarray[i]){ index1=i; } } if(--index1<0){ return false; } int index2=0; long max=Long.MIN_VALUE; for(int i=index1+1;iarray[i]){ index1=i; } } if(--index1<0){ return false; } int index2=0; int max=Integer.MIN_VALUE; for(int i=index1+1;i> boolean previousPermutation(E[] array){ int index1=0; for(int i=1;i0){ index1=i; } } if(--index1<0){ return false; } int index2=0; E max=MathFunction.min(array); for(int i=index1+1;i void reverseRange(E[] array,int l,int r){ while(l mo_sComparator(int M){ return (a,b)->a[0]/M!=b[0]/M?Integer.compare(a[0]/M,b[0]/M): Integer.compare(a[1]/M,b[1]/M)*((a[0]/M&1)==0?-1:1); } } class MathFunction{ static int[] numberForIntPrime={2,7,61}; static long[] numberForLongPrime={2,7,61,325,9375,28178,450775,9780504,1795265022}; static long gcd(long a,long b){ a=Math.abs(a); b=Math.abs(b); if(b==0){ return a; } long temp; while((temp=a%b)!=0){ a=b; b=temp; } return b; } static long lcm(long a,long b){ return a/gcd(a,b)*b; } static boolean isPrime(long n){ n=Math.abs(n); if(n==2L){ return true; } if(n==1L||(n&1L)==0L){ return false; } if(n<=4_759_123_141L){ return isPrimeForInt(n); } return isPrimeForBigInteger(n); } static boolean isPrimeForInt(long n){ long d=n-1; while((d&1)==0L){ d >>= 1; } for(long a: numberForIntPrime){ if(a>=n){ return true; } long t=d; long y=MathFunction.modPow(a,t,n); while(t>= 1; } BigInteger bigN=BigInteger.valueOf(n); BigInteger bigNSubOne=bigN.subtract(BigInteger.ONE); BigInteger bigD=BigInteger.valueOf(d); for(long a: numberForLongPrime){ if(a>=n){ return true; } BigInteger t=bigD; BigInteger y=BigInteger.valueOf(a).modPow(t,bigN); while(t.compareTo(bigNSubOne)<0&&!y.equals(BigInteger.ONE)&&!y.equals(bigNSubOne)){ y=y.multiply(y).mod(bigN); t=t.shiftLeft(1); } if(!y.equals(bigNSubOne)&&(t.intValue()&1)==0){ return false; } } return true; } static int[] primes(int num){ if(num<2){ return new int[0]; } BitSet numbers=new BitSet(num+1); numbers.set(2,num+1); int limit=(int)Math.sqrt(num); int bit=0; while( rangeCheckClose( bit=numbers.nextSetBit(bit+1), 2, limit)){ for(int j=bit*bit;j<=num;j+=bit){ numbers.clear(j); } } int[] answer=new int[numbers.cardinality()]; bit=0; for(int i=0;i0){ if((b&1)==1){ ans *= a; } a *= a; b >>= 1; } return ans; } static long modPow(long a,long b,long mod){ long ans=1; a %= mod; while(b>0){ if((b&1)==1){ ans *= a; } ans %= mod; a *= a; a %= mod; b >>= 1; } return ans; } static long fact(int N){ long ans=1; for(int i=2;i<=N;++i){ ans *= i; } return ans; } static long modFact(int N,long mod){ long ans=1; for(int i=2;i<=N;++i){ ans *= i; ans %= mod; } return ans; } static long combi(long n,long r){ if(r<0||n0||temp2>0){ return -1; } if(temp1==0&&temp2==0){ return 0; } return 1; } static int isCrossed(Point p1,Point p2,Point p3,Point p4){ return isCrossed(p1.x,p1.y,p2.x,p2.y,p3.x,p3.y,p4.x,p4.y); } static boolean isConvex(Point... points){ int n=points.length; if(n<3){ return false; } if(n==3){ return true; } boolean conv=true; for(int i=0;i=0; } return conv; } static long remainder(long num,long mod){ num %= mod; if(num<0){ num += mod; } return num; } static int digit(long num){ if(num<10L){ return 1; } if(num<100L){ return 2; } if(num<1000L){ return 3; } if(num<10000L){ return 4; } if(num<100000L){ return 5; } if(num<1000000L){ return 6; } if(num<10000000L){ return 7; } if(num<100000000L){ return 8; } if(num<1000000000L){ return 9; } if(num<10000000000L){ return 10; } if(num<100000000000L){ return 11; } if(num<1000000000000L){ return 12; } if(num<10000000000000L){ return 13; } if(num<100000000000000L){ return 14; } if(num<1000000000000000L){ return 15; } if(num<10000000000000000L){ return 16; } if(num<100000000000000000L){ return 17; } if(num<1000000000000000000L){ return 18; } return 19; } static int max(int... nums){ int ans=Integer.MIN_VALUE; for(int num: nums){ ans=Math.max(ans,num); } return ans; } static long max(long... nums){ long ans=Long.MIN_VALUE; for(long num: nums){ ans=Math.max(ans,num); } return ans; } static double max(double... nums){ double ans=-Double.MIN_VALUE; for(double num: nums){ ans=Math.max(ans,num); } return ans; } static > E max(E[] nums){ E ans=nums[0]; for(E value: nums){ if(ans.compareTo(value)<0){ ans=value; } } return ans; } static int min(int... nums){ int ans=Integer.MAX_VALUE; for(int num: nums){ ans=Math.min(ans,num); } return ans; } static long min(long... nums){ long ans=Long.MAX_VALUE; for(long num: nums){ ans=Math.min(ans,num); } return ans; } static double min(double... nums){ double ans=Double.MAX_VALUE; for(double num: nums){ ans=Math.min(ans,num); } return ans; } static > E min(E[] nums){ E ans=nums[0]; for(E value: nums){ if(ans.compareTo(value)>0){ ans=value; } } return ans; } static long sum(int... nums){ long ans=0; for(int num: nums){ ans += num; } return ans; } static long sum(long... nums){ long ans=0; for(long num: nums){ ans += num; } return ans; } static long modSum(long mod,int... nums){ long ans=0; for(int num: nums){ ans += num; ans %= mod; } if(ans<0){ ans += mod; } return ans; } static long modSum(long mod,long... nums){ long ans=0; for(long num: nums){ ans += num; ans %= mod; } if(ans<0){ ans += mod; } return ans; } static long sum(int[] nums,int from,int to){ long ans=0; for(int i=from;i> boolean rangeCheck(E num,E l,E r){ return 0<=num.compareTo(l)&&num.compareTo(r)<0; } static boolean rangeCheckOpen(int num,int l,int r){ return l> boolean rangeCheckOpen(E num,E l,E r){ return 0> boolean rangeCheckClose(E num,E l,E r){ return 0<=num.compareTo(l)&&num.compareTo(r)<=0; } static boolean rangeCheckSubClose(int num,int l,int r){ return l> boolean rangeCheckSubClose(E num,E l,E r){ return 0value){ b=c-1; } else{ a=(ans=c)+1; } } return ans; } static int downSearch(long[] array,long value){ int a=0, b=array.length-1, ans=-1, c; while(a-b<1){ c=(a+b)/2; if(array[c]>value){ b=c-1; } else{ a=(ans=c)+1; } } return ans; } static int downSearch(double[] array,double value){ int a=0, b=array.length-1, ans=-1, c; while(a-b<1){ c=(a+b)/2; if(array[c]>value){ b=c-1; } else{ a=(ans=c)+1; } } return ans; } static int downSearch(char[] array,int value){ int a=0, b=array.length-1, ans=-1, c; while(a-b<1){ c=(a+b)/2; if(array[c]>value){ b=c-1; } else{ a=(ans=c)+1; } } return ans; } static > int downSearch(E[] array,E value){ int a=0, b=array.length-1, ans=-1, c; while(a-b<1){ c=(a+b)/2; if(array[c].compareTo(value)>0){ b=c-1; } else{ a=(ans=c)+1; } } return ans; } static > int downSearch(List list,E value){ int a=0, b=list.size()-1, ans=-1, c; while(a-b<1){ c=(a+b)/2; if(list.get(c).compareTo(value)>0){ b=c-1; } else{ a=(ans=c)+1; } } return ans; } static int downSearch(int a,int b,int value,IntUnaryOperator func){ int ans=a-1, c; while(a-b<1){ c=(a+b)/2; if(func.applyAsInt(c)>value){ b=c-1; } else{ a=(ans=c)+1; } } return ans; } static long downSearch(long a,long b,long value,LongUnaryOperator func){ long ans=a-1, c; while(a-b<1){ c=(a+b)/2; if(func.applyAsLong(c)>value){ b=c-1; } else{ a=(ans=c)+1; } } return ans; } static double search(double a,double b,double value,DoubleUnaryOperator func){ double ans=a-Math.abs(a), c; for(int $=0;$value){ b=c; } else{ a=(ans=c); } } return ans; } static boolean contains(int[] array,int value){ int a=0, b=array.length-1, c; while(a-b<1){ c=(a+b)/2; if(array[c]>value){ b=c-1; } else if(array[c]value){ b=c-1; } else if(array[c]value){ b=c-1; } else if(array[c]value){ b=c-1; } else if(array[c]> boolean contains(E[] array,E value){ int a=0, b=array.length-1, c; while(a-b<1){ c=(a+b)/2; int result=array[c].compareTo(value); if(result>0){ b=c-1; } else if(result<0){ a=c+1; } else{ return true; } } return false; } static > boolean contains(List list,E value){ int a=0, b=list.size()-1, c; while(a-b<1){ c=(a+b)/2; int result=list.get(c).compareTo(value); if(result>0){ b=c-1; } else if(result<0){ a=c+1; } else{ return true; } } return false; } static boolean contains(int a,int b,int value,IntUnaryOperator func){ int c; while(a-b<1){ c=(a+b)/2; int num=func.applyAsInt(c); if(num>value){ b=c-1; } else if(numvalue){ b=c-1; } else if(numvalue){ b=c-1; } else if(numvalue){ b=c-1; } else if(array[c]value){ b=c-1; } else if(array[c]value){ b=c-1; } else if(array[c]value){ b=c-1; } else if(array[c]> int search(E[] array,E value){ int a=0, b=array.length-1, c; while(a-b<1){ c=(a+b)/2; int result=array[c].compareTo(value); if(result>0){ b=c-1; } else if(result<0){ a=c+1; } else{ return c; } } return -1; } static > int search(List list,E value){ int a=0, b=list.size()-1, c; while(a-b<1){ c=(a+b)/2; int result=list.get(c).compareTo(value); if(result>0){ b=c-1; } else if(result<0){ a=c+1; } else{ return c; } } return -1; } static int search(int a,int b,int value,IntUnaryOperator func){ int c; while(a-b<1){ c=(a+b)/2; int num=func.applyAsInt(c); if(num>value){ b=c-1; } else if(numvalue){ b=c-1; } else if(num=value){ b=(ans=c)-1; } else{ a=c+1; } } return ans; } static int upSearch(long[] array,long value){ int a=0, b=array.length-1, ans=array.length, c; while(a-b<1){ c=(a+b)/2; if(array[c]>=value){ b=(ans=c)-1; } else{ a=c+1; } } return ans; } static int upSearch(double[]array,double value){int a=0,b=array.length-1,ans=array.length,c;while(a-b<1){c=(a+b)/2;if(array[c]>=value)b=(ans=c)-1;else a=c+1;}return ans;} static int upSearch(char[]array,char value){int a=0,b=array.length-1,ans=array.length,c;while(a-b<1){c=(a+b)/2;if(array[c]>=value)b=(ans=c)-1;else a=c+1;}return ans;} static>int upSearch(E[]array,E value){int a=0,b=array.length-1,ans=array.length,c;while(a-b<1){c=(a+b)/2;if(array[c].compareTo(value)>=0)b=(ans=c)-1;else a=c+1;}return ans;} static>int upSearch(Listlist,E value){int a=0,b=list.size()-1,ans=list.size(),c;while(a-b<1){c=(a+b)/2;if(list.get(c).compareTo(value)>=0)b=(ans=c)-1;else a=c+1;}return ans;} static int upSearch(int a,int b,int value,IntUnaryOperator func){int ans=b+1,c;while(a-b<1){c=(a+b)/2;if(func.applyAsInt(c)>=value)b=(ans=c)-1;else a=c+1;}return ans;} static long upSearch(long a,long b,long value,LongUnaryOperator func){long ans=b+1,c;while(a-b<1){c=(a+b)/2;if(func.applyAsLong(c)>=value)b=(ans=c)-1;else a=c+1;}return ans;} static int underSearch(int[]array,int value){int a=0,b=array.length-1,ans=-1,c;while(a-b<1){c=(a+b)/2;if(array[c]>=value)b=c-1;else a=(ans=c)+1;}return ans;} static int underSearch(long[]array,long value){int a=0,b=array.length-1,ans=-1,c;while(a-b<1){c=(a+b)/2;if(array[c]>=value)b=c-1;else a=(ans=c)+1;}return ans;} static int underSearch(double[]array,double value){int a=0,b=array.length-1,ans=-1,c;while(a-b<1){c=(a+b)/2;if(array[c]>=value)b=c-1;else a=(ans=c)+1;}return ans;} static int underSearch(char[]array,char value){int a=0,b=array.length-1,ans=-1,c;while(a-b<1){c=(a+b)/2;if(array[c]>=value)b=c-1;else a=(ans=c)+1;}return ans;} static>int underSearch(E[]array,E value){int a=0,b=array.length-1,ans=-1,c;while(a-b<1){c=(a+b)/2;if(array[c].compareTo(value)>=0)b=c-1;else a=(ans=c)+1;}return ans;} static>int underSearch(Listlist,E value){int a=0,b=list.size()-1,ans=-1,c;while(a-b<1){c=(a+b)/2;if(list.get(c).compareTo(value)>=0)b=c-1;else a=(ans=c)+1;}return ans;} static int underSearch(int a,int b,int value,IntUnaryOperator func){int ans=a-1,c;while(a-b<1){c=(a+b)/2;if(func.applyAsInt(c)>=value)b=c-1;else a=(ans=c)+1;}return ans;} static long underSearch(long a,long b,long value,LongUnaryOperator func){long ans=a-1,c;while(a-b<1){c=(a+b)/2;if(func.applyAsLong(c)>=value)b=c-1;else a=(ans=c)+1;}return ans;} static int overSearch(int[]array,int value){int a=0,b=array.length-1,ans=array.length,c;while(a-b<1){c=(a+b)/2;if(array[c]>value)b=(ans=c)-1;else a=c+1;}return ans;} static int overSearch(long[]array,long value){int a=0,b=array.length-1,ans=array.length,c;while(a-b<1){c=(a+b)/2;if(array[c]>value)b=(ans=c)-1;else a=c+1;}return ans;} static int overSearch(double[]array,double value){int a=0,b=array.length-1,ans=array.length,c;while(a-b<1){c=(a+b)/2;if(array[c]>value)b=(ans=c)-1;else a=c+1;}return ans;} static int overSearch(char[]array,char value){int a=0,b=array.length-1,ans=array.length,c;while(a-b<1){c=(a+b)/2;if(array[c]>value)b=(ans=c)-1;else a=c+1;}return ans;} static>int overSearch(E[]array,E value){int a=0,b=array.length-1,ans=array.length,c;while(a-b<1){c=(a+b)/2;if(array[c].compareTo(value)>0)b=(ans=c)-1;else a=c+1;}return ans;} static>int overSearch(Listlist,E value){int a=0,b=list.size()-1,ans=list.size(),c;while(a-b<1){c=(a+b)/2;if(list.get(c).compareTo(value)>0)b=(ans=c)-1;else a=c+1;}return ans;} static int overSearch(int a,int b,int value,IntUnaryOperator func){int ans=b+1,c;while(a-b<1){c=(a+b)/2;if(func.applyAsInt(c)>value)b=(ans=c)-1;else a=c+1;}return ans;} static long overSearch(long a,long b,long value,LongUnaryOperator func){long ans=b+1,c;while(a-b<1){c=(a+b)/2;if(func.applyAsLong(c)>value)b=(ans=c)-1;else a=c+1;}return ans;} static int linearSearch(int[]array,int value){for(int i=0;i>int linearSearch(E[]array,E value){for(int i=0;i>int linearSearch(Listlist,E value){for(int i=0;i>= 1; } return a; } static Matrix modPow(Matrix original,Matrix pw,long exp,long mod){ Matrix a=original.copy(); Matrix b=pw.copy(); while(0>= 1; } return a; } long determinant(){ return determinant(matrix); } long modDeterminant(long mod){ return modDeterminant(matrix,mod); } static long modDeterminant(long[][] mat,long mod){ assert mat.length==mat[0].length; if(mat.length==1){ return mat[0][0]; } if(mat.length==2){ return (mat[0][0]*mat[1][1]-mat[0][1]*mat[1][0])%mod; } int N=mat.length; long[][]internalMatrix=new long[N][N]; for(int i=0;i, Cloneable{ BigInteger numerator,denominator; static RationalNumber ONE=new RationalNumber(BigInteger.ONE,BigInteger.ONE,false),TEN=new RationalNumber(BigInteger.TEN,BigInteger.ONE,false),ZERO=new RationalNumber(BigInteger.ZERO,BigInteger.ONE,false); public RationalNumber ( final long n, final long d ) { this( BigInteger.valueOf( n ), BigInteger.valueOf( d ), true ); } public RationalNumber ( final BigInteger n, final BigInteger d ) { this(n,d,true); } private RationalNumber ( BigInteger n, BigInteger d, final boolean needToReduce ) { if(needToReduce) { if ( d.equals( BigInteger.ZERO ) ) { throw new ArithmeticException( "/ by zero" ); } final BigInteger g = n.gcd( d ); if ( g.equals( BigInteger.ZERO ) ) { numerator = BigInteger.ZERO; denominator = BigInteger.ONE; } else { n = n.divide( g ); d = d.divide( g ); if ( d.compareTo( BigInteger.ZERO ) < 0 ) { denominator = d.negate(); numerator = n.negate(); } else { denominator = d; numerator = n; } } } else { numerator = n; denominator = d; } } public RationalNumber ( final String decimalString ) { this( decimalString, 10 ); } public RationalNumber ( final String str, final int radix ) { BigInteger n, d; if ( str.contains( "." ) ) { n = new BigInteger( str.replace( ".", "" ), radix ); d = BigInteger.valueOf( radix ).pow( str.length() - str.indexOf( "." ) - 1 ); final BigInteger g = n.gcd( d ); if ( g.equals( BigInteger.ZERO ) ) { numerator = BigInteger.ZERO; denominator = BigInteger.ONE; } else { n = n.divide( g ); d = d.divide( g ); if ( d.compareTo( BigInteger.ZERO ) < 0 ) { denominator = d.negate(); numerator = n.negate(); } else { denominator = d; numerator = n; } } } else { numerator = new BigInteger( str, radix ); denominator = BigInteger.ONE; } } public static RationalNumber valueOf ( final double num ) { final long n = Double.doubleToLongBits( num ); final long value = ( ( ( 1L << 52 ) - 1 ) & n ) | ( 1L << 52 ); final long exp = 1075 - ( ( ( 1 << 11 ) - 1 ) & ( n >> 52 ) ); BigInteger nn = BigInteger.valueOf( value ); final BigInteger dd = BigInteger.ONE.shiftLeft( ( int )exp ); if ( num < 0 ) { nn = nn.negate(); } return new RationalNumber( nn, dd, true ); } public static RationalNumber valueOf ( final long num ) { final BigInteger n = BigInteger.valueOf( num ); final BigInteger d = BigInteger.ONE; return new RationalNumber( n, d, false ); } public RationalNumber add ( final RationalNumber rn ) { final BigInteger n = numerator.multiply( rn.denominator ).add( rn.numerator.multiply( denominator ) ); final BigInteger d = denominator.multiply( rn.denominator ); return new RationalNumber( n, d, true ); } public RationalNumber add ( final BigInteger bi ) { final BigInteger n = numerator.add( bi.multiply( denominator ) ); return new RationalNumber(n,denominator,false ); } public RationalNumber add ( final long l ) { final BigInteger n = numerator.add( BigInteger.valueOf(l) ); return new RationalNumber(n,denominator,false ); } public RationalNumber subtract ( final RationalNumber rn ) { final BigInteger n = numerator.multiply( rn.denominator ).subtract( rn.numerator.multiply( denominator ) ); final BigInteger d = denominator.multiply( rn.denominator ); return new RationalNumber( n, d, true ); } public RationalNumber subtract ( final BigInteger bi ) { final BigInteger n = numerator.subtract( bi.multiply( denominator ) ); return new RationalNumber(n,denominator,false ); } public RationalNumber subtract ( final long l ) { final BigInteger n = numerator.subtract( BigInteger.valueOf(l) ); return new RationalNumber(n,denominator,false ); } public RationalNumber multiply ( final RationalNumber rn ) { final BigInteger n = numerator.multiply( rn.numerator ); final BigInteger d = denominator.multiply( rn.denominator ); return new RationalNumber( n, d, true ); } public RationalNumber multiply ( final BigInteger bi ) { final BigInteger n = numerator.multiply( bi ); return new RationalNumber(n,denominator,true ); } public RationalNumber multiply ( final long l ) { final BigInteger n = numerator.multiply( BigInteger.valueOf(l) ); return new RationalNumber(n,denominator,true ); } public RationalNumber divide ( final RationalNumber rn ) { final BigInteger n = numerator.multiply( rn.denominator ); final BigInteger d = denominator.multiply( rn.numerator ); return new RationalNumber( n, d, true ); } public RationalNumber divide ( final BigInteger bi ) { final BigInteger d = denominator.multiply( bi ); return new RationalNumber(numerator,d,true ); } public RationalNumber divide ( final long l ) { final BigInteger d = denominator.multiply( BigInteger.valueOf(l) ); return new RationalNumber(numerator,d,true ); } public RationalNumber pow ( long e ) { BigInteger baseN; BigInteger baseD; if ( e < 0 ) { baseN = denominator; baseD = numerator; } else { baseN = numerator; baseD = denominator; } if ( e == Long.MIN_VALUE ) { int count = 63; while ( count-- > 0 ) { baseN = baseN.multiply( baseN ); baseD = baseD.multiply( baseD ); } return new RationalNumber( baseN, baseD, false ); } else { e = Math.abs( e ); BigInteger ansN = BigInteger.ONE; BigInteger ansD = BigInteger.ONE; while ( e > 0 ) { if ( ( e & 1 ) == 1 ) { ansN = ansN.multiply( baseN ); ansD = ansD.multiply( baseD ); } baseN = baseN.multiply( baseN ); baseD = baseD.multiply( baseD ); e >>= 1; } return new RationalNumber( ansN, ansD, false ); } } public RationalNumber sqrt ( final int len ) { if ( this.signum() < 0 ) { throw new ArithmeticException( "Negative RationalNumber" ); } RationalNumber ans = new RationalNumber( numerator.sqrt(), denominator.sqrt(), true ); final RationalNumber TWO = new RationalNumber( 2, 1 ); String before = ans.toDecimalString( len ); for ( int i = 0; i < 1000; i++ ) { ans = ans.subtract( ans.multiply( ans ).subtract( this ).divide( ans.multiply( TWO ) ) ); final String str = ans.toDecimalString( len ); if ( before.equals( str ) ) { break; } before = str; } return ans; } public RationalNumber abs () { return new RationalNumber( numerator.abs(), denominator, false ); } public RationalNumber negate () { return new RationalNumber( numerator.negate(), denominator, false ); } public BigInteger[] divideAndRemainder () { final BigInteger[] ans = new BigInteger[2]; ans[0] = toBigInteger(); ans[1] = numerator.mod( denominator ); return ans; } public int signum () { return numerator.signum(); } public RationalNumber inverse () { return new RationalNumber( denominator, numerator, false ); } public RationalNumber movePointLeft ( final int n ) { final RationalNumber base = TEN.inverse().pow( n ); return multiply( base ); } public RationalNumber movePointRight ( final int n ) { final RationalNumber base = TEN.pow( n ); return multiply( base ); } @Override public String toString () { return numerator.toString() + '/' + denominator.toString(); } public String toDecimalString ( final int n ) { final StringBuilder ans = new StringBuilder(); ans.append( numerator.divide( denominator ) ); BigInteger num = numerator.abs().mod( denominator ); if ( n > 0 && num.compareTo( BigInteger.ZERO ) > 0 ) { ans.append( '.' ); } for ( int i = 0; i < n; i++ ) { int count = 0; num = num.multiply( BigInteger.TEN ); while ( num.compareTo( denominator ) >= 0 ) { num = num.subtract( denominator ); count++; } ans.append( count ); if ( num.equals( BigInteger.ZERO ) ) { break; } } return ans.toString(); } BigInteger toBigInteger () { return numerator.divide( denominator ); } @Override public int compareTo (RationalNumber rn){if(equals(rn))return 0;final BigInteger num1=toBigInteger(),num2=rn.toBigInteger();int result=num1.compareTo(num2);if(result!=0)return result;BigInteger n1=numerator.mod(denominator),n2=rn.numerator.mod(rn.denominator);while(true){int count1=0;n1=n1.multiply(BigInteger.TEN);while(n1.compareTo(denominator)>=0){n1=n1.subtract(denominator);count1++;}int count2=0;n2=n2.multiply(BigInteger.TEN);while(n2.compareTo(rn.denominator)>=0){n2=n2.subtract(rn.denominator);count2++;}if(count1!=count2)return Integer.signum(count1-count2);}} @Override public int hashCode(){return(numerator.hashCode()<<4)^denominator.hashCode();} @Override public RationalNumber clone(){try{return(RationalNumber)super.clone();}catch(CloneNotSupportedException e){throw new RuntimeException(e);}} @Override public boolean equals(Object o){return o instanceof RationalNumber rn?numerator.equals(rn.numerator)&&denominator.equals(rn.denominator):false;} @Override public double doubleValue(){return Double.parseDouble(toDecimalString(16));} @Override public float floatValue(){return Float.parseFloat(toDecimalString(8));} @Override public int intValue(){return toBigInteger().intValue();} @Override public long longValue(){return toBigInteger().longValue();} } class SimpleScanner{ int BUFF_SIZE=1<<17,point,length; InputStream is; byte[]buff; SimpleScanner(InputStream is){this.is=is;buff=new byte[BUFF_SIZE];point=length=0;} void reload(){do{try{length=is.read(buff,point=0,BUFF_SIZE);}catch(IOException e){e.printStackTrace();System.exit(1);}}while(length==-1);} byte read(){if(point==length)reload();return buff[point++];} byte nextByte(){var c=read();while(c<=' ')c=read();return c;} int nextInt(){int ans=0;var c=nextByte();var negate=c=='-';if(!MathFunction.rangeCheckClose(c,'0','9'))c=read();while(MathFunction.rangeCheckClose(c,'0','9')){ans=ans*10+c-'0';c=read();}return negate?-ans:ans;} long nextLong(){long ans=0;var c=nextByte();var negate=c=='-';if(!MathFunction.rangeCheckClose(c,'0','9'))c=read();while(MathFunction.rangeCheckClose(c,'0','9')){ans=ans*10L+c-'0';c=read();}return negate?-ans:ans;} char nextChar(){return(char)nextByte();} String next(){var ans=new StringBuilder();var c=nextByte();while(c>' '){ans.append((char)c);c=read();}return ans.toString();} BigInteger nextBigInteger(){return new BigInteger(next());} byte[]nextByte(int n){var ans=new byte[n];for(int i=0;i0;i--){integerBuffer[i]=(byte)(num%10+ZERO);num/=10;}if(l<0)write(integerBuffer,0,len+1);else write(integerBuffer,1,len);}} void print(float f){write(String.valueOf(f).toCharArray());} void print(double d){write(String.valueOf(d).toCharArray());} void print(char[]s){write(s);} void print(Object obj){write(obj.toString().toCharArray());} void println(){newLine();} void println(boolean x){print(x);println();} void println(char x){print(x);println();} void println(int x){print(x);println();} void println(long x){print(x);println();} void println(float x){print(x);println();} void println(double x){print(x);println();} void println(char[]x){print(x);println();} void println(String x){print(x);println();} void println(Object x){print(x);println();} SimpleWriter printf(String format,Object...args){print(String.format(format,args));return this;} SimpleWriter append(CharSequence csq){write(String.valueOf(csq).toCharArray());return this;} SimpleWriter append(CharSequence csq,int start,int end){if(csq==null)csq="null";return append(csq.subSequence(start,end));} SimpleWriter append(char c){write(c);return this;} void print(int[]array){print(array,' ');} void print(int[]array,String str){if(array.length==0)return;print(array[0]);for(int i=1;ivoid print(E[]array){print(array,' ');} void print(E[]array,String str){print(array[0]);for(int i=1;ivoid print(E[]array,char c){print(array[0]);for(int i=1;ivoid print(E[][]arrays){print(arrays,' ');} void print(E[][]arrays,String str){print(arrays[0],str);for(int i=1;ivoid print(E[][]arrays,char c){print(arrays[0],c);for(int i=1;ivoid println(E[]array){println(array,' ');} void println(E[]array,String str){print(array,str);println();} void println(E[]array,char c){print(array,c);println();} void println(E[][]arrays){println(arrays,' ');} void println(E[][]arrays,String str){print(arrays,str);println();} void println(E[][]arrays,char c){print(arrays,c);println();} void println(Listlist){println(list,' ');} void println(Listlist,String str){if(list.size()>0){print(list.get(0));for(int i=1;ivoid println(Listlist,char c){if(list.size()>0){print(list.get(0));for(int i=1;i0){out.write(buf,0,count);count=0;}} void write(int b)throws IOException{if(count>=buf.length)flushBuffer();buf[count++]=(byte)b;} void write(char[]ch,int off,int len)throws IOException{if(len>=buf.length){flushBuffer();out.write(parseByteArray(ch,off,len),0,len);return;}if(len>buf.length-count)flushBuffer();for(int i=0;i=buf.length){flushBuffer();out.write(b,off,len);return;}if(len>buf.length-count)flushBuffer();System.arraycopy(b,off,buf,count,len);count+=len;} void flush() throws IOException{flushBuffer();out.flush();} void close() throws IOException{flush();out.close();out=null;} } }