結果
| 問題 |
No.2825 Sum of Scores of Sets of Specified Sections
|
| コンテスト | |
| ユーザー |
 viral8
|
| 提出日時 | 2024-04-27 11:21:26 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 63,409 bytes |
| コンパイル時間 | 4,746 ms |
| コンパイル使用メモリ | 101,804 KB |
| 実行使用メモリ | 60,692 KB |
| 最終ジャッジ日時 | 2024-07-26 20:01:58 |
| 合計ジャッジ時間 | 14,213 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 27 WA * 5 |
ソースコード
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;i<H;i++)
for(int j=0;j<W;j++)
A.set(i,j,sc.nextInt());
var B=new Matrix(W,H);
for(int i=0;i<H;i++)
for(int j=0;j<W;j++)
B.set(j,i,sc.nextInt());
var C=A.modMultiply(B,998244353);
for(int i=0;i<H;i++)
C.set(i,i,(C.get(i,i)+1)%998244353);
out.println(C.modDeterminant(998244353)-1);
out.close();
}
}
/*////////////////////////////////////////////////////////////////////////////////////////////
* My Library *
@author viral
*/////////////////////////////////////////////////////////////////////////////////////////////
class ArrayFunction{
static void countSort(int[] array,int maximumLimit){
countSort(array,0,array.length,maximumLimit);
}
static void countSort(int[] array,int l,int r,int maximumLimit){
int[] list=new int[maximumLimit+1];
for(int i=l;i<r;++i){
++list[array[i]];
}
int temp=l;
for(int i=0;i<list.length;++i){
while(list[i]-->0){
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;i<r;i++){
int j=i;
int num=array[j];
while(l<j&&array[j-1]>num){
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;i<r;i++){
int j=i;
long num=array[j];
while(l<j&&array[j-1]>num){
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;i<r;i++){
int j=i;
char num=array[j];
while(l<j&&array[j-1]>num){
array[j]=array[j-1];
--j;
}
array[j]=num;
}
}
static <E extends Comparable<E>> void insertSort(E[] array){
insertSort(array,0,array.length);
}
static <E extends Comparable<E>> void insertSort(E[] array,int l,int r){
for(int i=l+1;i<r;i++){
int j=i;
E num=array[j];
while(l<j&&array[j-1].compareTo(num)>0){
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<r;i++){
int j=i;
int num=array[j];
while(l<j&&array[j-1]<num){
array[j]=array[j-1];
--j;
}
array[j]=num;
}
}
static void reverseInsertSort(long[] array){
reverseInsertSort(array,0,array.length);
}
static void reverseInsertSort(long[] array,int l,int r){
for(int i=l+1;i<r;i++){
int j=i;
long num=array[j];
while(l<j&&array[j-1]<num){
array[j]=array[j-1];
--j;
}
array[j]=num;
}
}
static void reverseInsertSort(char[] array){
reverseInsertSort(array,0,array.length);
}
static void reverseInsertSort(char[] array,int l,int r){
for(int i=l+1;i<r;i++){
int j=i;
char num=array[j];
while(l<j&&array[j-1]<num){
array[j]=array[j-1];
--j;
}
array[j]=num;
}
}
static <E extends Comparable<E>> void reverseInsertSort(E[] array){
reverseInsertSort(array,0,array.length);
}
static <E extends Comparable<E>> void reverseInsertSort(E[] array,int l,int r){
for(int i=l+1;i<r;i++){
int j=i;
E num=array[j];
while(l<j&&array[j-1].compareTo(num)<0){
array[j]=array[j-1];
--j;
}
array[j]=num;
}
}
static int[][] rotateR(int[][] array){
int[][] ans=new int[array[0].length][array.length];
for(int i=0;i<ans.length;++i){
for(int j=0;j<ans[i].length;++j){
ans[i][j]=array[ans[i].length-j-1][i];
}
}
return ans;
}
static long[][] rotateR(long[][] array){
long[][] ans=new long[array[0].length][array.length];
for(int i=0;i<ans.length;++i){
for(int j=0;j<ans[i].length;++j){
ans[i][j]=array[ans[i].length-j-1][i];
}
}
return ans;
}
static char[][] rotateR(char[][] array){
char[][] ans=new char[array[0].length][array.length];
for(int i=0;i<ans.length;++i){
for(int j=0;j<ans[i].length;++j){
ans[i][j]=array[ans[i].length-j-1][i];
}
}
return ans;
}
static double[][] rotateR(double[][] array){
double[][] ans=new double[array[0].length][array.length];
for(int i=0;i<ans.length;++i){
for(int j=0;j<ans[i].length;++j){
ans[i][j]=array[ans[i].length-j-1][i];
}
}
return ans;
}
static boolean[][] rotateR(boolean[][] array){
boolean[][] ans=new boolean[array[0].length][array.length];
for(int i=0;i<ans.length;++i){
for(int j=0;j<ans[i].length;++j){
ans[i][j]=array[ans[i].length-j-1][i];
}
}
return ans;
}
static <E> E[][] rotateR(E[][] array,E[][] ans){
for(int i=0;i<ans.length;++i){
for(int j=0;j<ans[i].length;++j){
ans[i][j]=array[ans[i].length-j-1][i];
}
}
return ans;
}
static int[][] rotateL(int[][] array){
int[][] ans=new int[array[0].length][array.length];
for(int i=0;i<ans.length;++i){
int index=i;
Arrays.setAll(ans[i],k->array[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;i<ans.length;++i){
int index=i;
Arrays.setAll(ans[i],k->array[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<ans.length;++i){
for(int j=0;j<ans[i].length;++j){
ans[i][j]=array[j][ans.length-i-1];
}
}
return ans;
}
static double[][] rotateL(double[][] array){
double[][] ans=new double[array[0].length][array.length];
for(int i=0;i<ans.length;++i){
for(int j=0;j<ans[i].length;++j){
ans[i][j]=array[j][ans.length-i-1];
}
}
return ans;
}
static boolean[][] rotateL(boolean[][] array){
boolean[][] ans=new boolean[array[0].length][array.length];
for(int i=0;i<ans.length;++i){
for(int j=0;j<ans[i].length;++j){
ans[i][j]=array[j][ans.length-i-1];
}
}
return ans;
}
static <E> E[][] rotateL(E[][] array,E[][] ans){
for(int i=0;i<ans.length;++i){
for(int j=0;j<ans[i].length;++j){
ans[i][j]=array[j][ans.length-i-1];
}
}
return ans;
}
static int lis(int[] array){
return lis(array,false);
}
static int lis(int[][] arrays,int p){
return lis(arrays,p,false);
}
static int lis(long[] array){
return lis(array,false);
}
static int lis(long[][] arrays,int p){
return lis(arrays,p,false);
}
static int lis(int[] array,boolean include){
int[] list=new int[array.length];
Arrays.fill(list,Integer.MAX_VALUE);
for(int num: array){
int index=include?Searcher.overSearch(list,num):Searcher.upSearch(list,num);
list[index]=Math.min(list[index],num);
}
int answer=Searcher.underSearch(list,Integer.MAX_VALUE);
return answer+1;
}
static int lis(int[][] arrays,int p,boolean include){
int[] list=new int[arrays.length];
Arrays.fill(list,Integer.MAX_VALUE);
for(int[] array: arrays){
int index=include?Searcher.overSearch(list,array[p]):Searcher.upSearch(list,array[p]);
list[index]=Math.min(list[index],array[p]);
}
int answer=Searcher.underSearch(list,Integer.MAX_VALUE);
return answer+1;
}
static int lis(long[] array,boolean include){
long[] list=new long[array.length];
Arrays.fill(list,Long.MAX_VALUE);
for(long num: array){
int index=include?Searcher.overSearch(list,num):Searcher.upSearch(list,num);
list[index]=Math.min(list[index],num);
}
int answer=Searcher.underSearch(list,Long.MAX_VALUE);
return answer+1;
}
static int lis(long[][] arrays,int p,boolean include){
long[] list=new long[arrays.length];
Arrays.fill(list,Long.MAX_VALUE);
for(long[] array: arrays){
int index=include?Searcher.overSearch(list,array[p]):Searcher.upSearch(list,array[p]);
list[index]=Math.min(list[index],array[p]);
}
int answer=Searcher.underSearch(list,Long.MAX_VALUE);
return answer+1;
}
static int[][] topologicalSort(ArrayList<ArrayList<Integer>> route){
int[] count=new int[route.size()];
int pathCount=0;
for(ArrayList<Integer> path: route){
for(int point: path){
++pathCount;
++count[point];
}
}
ArrayDeque<Integer> deq=new ArrayDeque<>();
for(int i=1;i<count.length;++i){
if(count[i]==0){
deq.add(i);
}
}
int[][] ans=new int[pathCount][2];
int index=0;
while(deq.size()>0){
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<Integer> deq=new ArrayDeque<>();
for(int i=1;i<count.length;++i){
if(count[i]==0){
deq.add(i);
}
}
int[][] ans=new int[pathCount][2];
int index=0;
while(deq.size()>0){
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 <E> 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 <E> 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<array.length;++i){
if(array[i-1]<array[i]){
index1=i;
}
}
if(--index1<0){
return false;
}
int index2=0;
int min=Integer.MAX_VALUE;
for(int i=index1+1;i<array.length;++i){
if(MathFunction.rangeCheckOpen(array[i],array[index1],min)){
min=array[i];
index2=i;
}
}
swap(array,index1,index2);
reverseRange(array,index1+1,array.length);
insertSort(array,index1+1,array.length);
return true;
}
static boolean nextPermutation(long[] array){
int index1=0;
for(int i=1;i<array.length;++i){
if(array[i-1]<array[i]){
index1=i;
}
}
if(--index1<0){
return false;
}
int index2=0;
long min=Long.MAX_VALUE;
for(int i=index1+1;i<array.length;++i){
if(MathFunction.rangeCheckOpen(array[i],array[index1],min)){
min=array[i];
index2=i;
}
}
swap(array,index1,index2);
reverseRange(array,index1+1,array.length);
insertSort(array,index1+1,array.length);
return true;
}
static boolean nextPermutation(char[] array){
int index1=0;
for(int i=1;i<array.length;++i){
if(array[i-1]<array[i]){
index1=i;
}
}
if(--index1<0){
return false;
}
int index2=0;
int min=Integer.MAX_VALUE;
for(int i=index1+1;i<array.length;++i){
if(MathFunction.rangeCheckOpen(array[i],array[index1],min)){
min=array[i];
index2=i;
}
}
swap(array,index1,index2);
reverseRange(array,index1+1,array.length);
insertSort(array,index1+1,array.length);
return true;
}
static <E extends Comparable<E>> boolean nextPermutation(E[] array){
int index1=0;
for(int i=1;i<array.length;++i){
if(array[i-1].compareTo(array[i])<0){
index1=i;
}
}
if(--index1<0){
return false;
}
int index2=0;
E min=MathFunction.max(array);
for(int i=index1+1;i<array.length;++i){
if(MathFunction.rangeCheckSubClose(array[i],array[index1],min)){
min=array[i];
index2=i;
}
}
swap(array,index1,index2);
reverseRange(array,index1+1,array.length);
insertSort(array,index1+1,array.length);
return true;
}
static boolean previousPermutation(int[] array){
int index1=0;
for(int i=1;i<array.length;++i){
if(array[i-1]>array[i]){
index1=i;
}
}
if(--index1<0){
return false;
}
int index2=0;
int max=Integer.MIN_VALUE;
for(int i=index1+1;i<array.length;++i){
if(MathFunction.rangeCheckOpen(array[i],max,array[index1])){
max=array[i];
index2=i;
}
}
swap(array,index1,index2);
reverseRange(array,index1+1,array.length);
reverseInsertSort(array,index1+1,array.length);
return true;
}
static boolean previousPermutation(long[] array){
int index1=0;
for(int i=1;i<array.length;++i){
if(array[i-1]>array[i]){
index1=i;
}
}
if(--index1<0){
return false;
}
int index2=0;
long max=Long.MIN_VALUE;
for(int i=index1+1;i<array.length;++i){
if(MathFunction.rangeCheckOpen(array[i],max,array[index1])){
max=array[i];
index2=i;
}
}
swap(array,index1,index2);
reverseRange(array,index1+1,array.length);
reverseInsertSort(array,index1+1,array.length);
return true;
}
static boolean previousPermutation(char[] array){
int index1=0;
for(int i=1;i<array.length;++i){
if(array[i-1]>array[i]){
index1=i;
}
}
if(--index1<0){
return false;
}
int index2=0;
int max=Integer.MIN_VALUE;
for(int i=index1+1;i<array.length;++i){
if(MathFunction.rangeCheckOpen(array[i],max,array[index1])){
max=array[i];
index2=i;
}
}
swap(array,index1,index2);
reverseRange(array,index1+1,array.length);
reverseInsertSort(array,index1+1,array.length);
return true;
}
static <E extends Comparable<E>> boolean previousPermutation(E[] array){
int index1=0;
for(int i=1;i<array.length;++i){
if(array[i-1].compareTo(array[i])>0){
index1=i;
}
}
if(--index1<0){
return false;
}
int index2=0;
E max=MathFunction.min(array);
for(int i=index1+1;i<array.length;++i){
if(MathFunction.rangeCheck(array[i],max,array[index1])){
max=array[i];
index2=i;
}
}
swap(array,index1,index2);
reverseRange(array,index1+1,array.length);
reverseInsertSort(array,index1+1,array.length);
return true;
}
static int[] reBuild(int[] array,IntUnaryOperator func){
int[] ans=new int[array.length];
for(int i=0;i<array.length;++i){
ans[i]=func.applyAsInt(array[i]);
}
return ans;
}
static int[] reBuild(int[] array,IntBinaryOperator func){
int[] ans=new int[array.length];
for(int i=0;i<array.length;++i){
ans[i]=func.applyAsInt(i,array[i]);
}
return ans;
}
static long[] reBuild(long[] array,LongUnaryOperator func){
long[] ans=new long[array.length];
for(int i=0;i<array.length;++i){
ans[i]=func.applyAsLong(array[i]);
}
return ans;
}
static long[] reBuild(long[] array,LongBinaryOperator func){
long[] ans=new long[array.length];
for(int i=0;i<array.length;++i){
ans[i]=func.applyAsLong(i,array[i]);
}
return ans;
}
static void computeByArray(int[] array,IntConsumer func){
for(int num: array){
func.accept(num);
}
}
static void reverseRange(int[] array,int l,int r){
while(l<r)
swap(array,l++,--r);
}
static void reverseRange(long[] array,int l,int r){
while(l<r)
swap(array,l++,--r);
}
static void reverseRange(double[] array,int l,int r){
while(l<r)
swap(array,l++,--r);
}
static void reverseRange(char[] array,int l,int r){
while(l<r)
swap(array,l++,--r);
}
static void reverseRange(boolean[] array,int l,int r){
while(l<r)
swap(array,l++,--r);
}
static <E> void reverseRange(E[] array,int l,int r){
while(l<r)
swap(array,l++,--r);
}
static Comparator<int[]> 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<n-1L&&y!=1&&y!=n-1){
y=y*y%n;
t <<= 1;
}
if(y!=n-1&&(t&1L)==0){
return false;
}
}
return true;
}
static boolean isPrimeForBigInteger(long n){
long d=n-1L;
while((d&1)==0L){
d >>= 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;i<answer.length;++i)
bit=(answer[i]=numbers.nextSetBit(bit+1));
return answer;
}
static long pow(long a,long b){
long ans=1;
while(b>0){
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||n<r){
return 0;
}
long ans=1;
r=Math.min(n-r,r);
for(int i=0;i<r;++i){
ans *= n-i;
ans /= i+1;
}
return ans;
}
static long modCombi(long n,long r,long mod){
if(r<0||n<r){
return 0;
}
long ans=1;
r=Math.min(n-r,r);
for(int i=0;i<r;++i){
ans *= (n-i)%mod;
ans %= mod;
ans *= modPow(i+1,mod-2,mod);
ans %= mod;
}
return ans;
}
static int isCrossed(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
long s1=(long)(x1-x2)*(y3-y1)-(long)(y1-y2)*(x3-x1);
long t1=(long)(x1-x2)*(y4-y1)-(long)(y1-y2)*(x4-x1);
long s2=(long)(x3-x4)*(y1-y3)-(long)(y3-y4)*(x1-x3);
long t2=(long)(x3-x4)*(y2-y3)-(long)(y3-y4)*(x2-x3);
long temp1=s1*t1;
long temp2=s2*t2;
if(temp1>0||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<n;++i){
int result=isCrossed(points[i],points[(i+2)%n],points[(i+1)%n],points[(i+1+n/2)%n]);
conv &= result>=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 extends Comparable<E>> 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 extends Comparable<E>> 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<to;++i){
ans += nums[i];
}
return ans;
}
static long sum(long[] nums,int from,int to){
long ans=0;
for(int i=from;i<to;++i){
ans += nums[i];
}
return ans;
}
static long modSum(int[] nums,int from,int to,long mod){
long ans=0;
for(int i=from;i<to;++i){
ans += nums[i];
ans %= mod;
}
if(ans<0){
ans += mod;
}
return ans;
}
static long modSum(long[] nums,int from,int to,long mod){
long ans=0;
for(int i=from;i<to;++i){
ans += nums[i];
ans %= mod;
}
if(ans<0){
ans += mod;
}
return ans;
}
static boolean rangeCheck(int num,int l,int r){
return l<=num&&num<r;
}
static boolean rangeCheck(long num,long l,long r){
return l<=num&&num<r;
}
static boolean rangeCheck(double num,double l,double r){
return l<=num&&num<r;
}
static <E extends Comparable<E>> 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<num&&num<r;
}
static boolean rangeCheckOpen(long num,long l,long r){
return l<num&&num<r;
}
static boolean rangeCheckOpen(double num,double l,double r){
return l<num&&num<r;
}
static <E extends Comparable<E>> boolean rangeCheckOpen(E num,E l,E r){
return 0<num.compareTo(l)&&num.compareTo(r)<0;
}
static boolean rangeCheckClose(int num,int l,int r){
return l<=num&&num<=r;
}
static boolean rangeCheckClose(long num,long l,long r){
return l<=num&&num<=r;
}
static boolean rangeCheckClose(double num,double l,double r){
return l<=num&&num<=r;
}
static <E extends Comparable<E>> 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<num&&num<=r;
}
static boolean rangeCheckSubClose(long num,long l,long r){
return l<num&&num<=r;
}
static boolean rangeCheckSubClose(double num,double l,double r){
return l<num&&num<=r;
}
static <E extends Comparable<E>> boolean rangeCheckSubClose(E num,E l,E r){
return 0<num.compareTo(l)&&num.compareTo(r)<=0;
}
static int mex(int... nums){
BitSet set=new BitSet(nums.length);
for(int num: nums)
if(num<nums.length)
set.set(num);
return set.nextClearBit(0);
}
}
class Searcher{
static int CYCLE_COUNT=Double.MAX_EXPONENT+53;
static int downSearch(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 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 <E extends Comparable<E>> 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 <E extends Comparable<E>> int downSearch(List<E> 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;$<CYCLE_COUNT;++$){
c=(a+b)/2;
if(func.applyAsDouble(c)>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){
a=c+1;
}
else{
return true;
}
}
return false;
}
static boolean contains(long[] array,long 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){
a=c+1;
}
else{
return true;
}
}
return false;
}
static boolean contains(double[] array,double 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){
a=c+1;
}
else{
return true;
}
}
return false;
}
static boolean contains(char[] array,char 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){
a=c+1;
}
else{
return true;
}
}
return false;
}
static <E extends Comparable<E>> 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 <E extends Comparable<E>> boolean contains(List<E> 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(num<value){
a=c+1;
}
else{
return true;
}
}
return false;
}
static boolean contains(long a,long b,long value,LongUnaryOperator func){
long c;
while(a-b<1){
c=(a+b)/2;
long num=func.applyAsLong(c);
if(num>value){
b=c-1;
}
else if(num<value){
a=c+1;
}
else{
return true;
}
}
return false;
}
static boolean contains(double a,double b,double value,DoubleUnaryOperator func){
double c;
for(int $=0;$<CYCLE_COUNT;++$){
c=(a+b)/2;
double num=func.applyAsDouble(c);
if(num>value){
b=c-1;
}
else if(num<value){
a=c+1;
}
else{
return true;
}
}
return false;
}
static int search(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){
a=c+1;
}
else{
return c;
}
}
return -1;
}
static int search(long[] array,long 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){
a=c+1;
}
else{
return c;
}
}
return -1;
}
static int search(double[] array,double 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){
a=c+1;
}
else{
return c;
}
}
return -1;
}
static int search(char[] array,char 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){
a=c+1;
}
else{
return c;
}
}
return -1;
}
static <E extends Comparable<E>> 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 <E extends Comparable<E>> int search(List<E> 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(num<value){
a=c+1;
}
else{
return c;
}
}
return a-1;
}
static long search(long a,long b,long value,LongUnaryOperator func){
long c;
while(a-b<1){
c=(a+b)/2;
long num=func.applyAsLong(c);
if(num>value){
b=c-1;
}
else if(num<value){
a=c+1;
}
else{
return c;
}
}
return a-1;
}
static int upSearch(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 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<E extends Comparable<E>>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<E extends Comparable<E>>int upSearch(List<E>list,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<E extends Comparable<E>>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<E extends Comparable<E>>int underSearch(List<E>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 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<E extends Comparable<E>>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<E extends Comparable<E>>int overSearch(List<E>list,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<array.length;++i)if(array[i]==value)return i;return-1;}
static int linearSearch(long[]array,long value){for(int i=0;i<array.length;++i)if(array[i]==value)return i;return-1;}
static int linearSearch(double[]array,double value){for(int i=0;i<array.length;++i)if(array[i]==value)return i;return-1;}
static int linearSearch(char[]array,char value){for(int i=0;i<array.length;++i)if(array[i]==value)return i;return-1;}
static<E extends Comparable<E>>int linearSearch(E[]array,E value){for(int i=0;i<array.length;++i)if(array[i].compareTo(value)==0)return i;return-1;}
static<E extends Comparable<E>>int linearSearch(List<E>list,E value){for(int i=0;i<list.size();++i)if(list.get(i).compareTo(value)==0)return i;return-1;}
}
class Matrix{
long[][] matrix;
Matrix(int H,int W,long def){
matrix=new long[H][W];
if(def!=0){
for(long[] mat: matrix){
Arrays.fill(mat,def);
}
}
}
Matrix(int H,int W){
this(H,W,0);
}
Matrix(Dimension d,long def){
this(d.height,d.width,def);
}
Matrix(long[][] mat){
matrix=new long[mat.length][];
for(int i=0;i<mat.length;++i){
matrix[i]=Arrays.copyOf(mat[i],mat[i].length);
}
}
long get(int i,int j){
return matrix[i][j];
}
long set(int i,int j,long value){
return matrix[i][j]=value;
}
Matrix copy(){
return new Matrix(matrix);
}
Dimension size(){
return new Dimension(matrix[0].length,matrix.length);
}
Matrix add(Matrix m){
if(!size().equals(m.size())){
throw new IllegalArgumentException("matrix size is not same");
}
Matrix ans=new Matrix(size(),0);
for(int i=0;i<matrix.length;++i){
for(int j=0;j<matrix[i].length;++j){
ans.set(i,j,matrix[i][j]+m.get(i,j));
}
}
return ans;
}
Matrix subtract(Matrix m){
if(!size().equals(m.size())){
throw new IllegalArgumentException("matrix size is not same");
}
Matrix ans=new Matrix(size(),0);
for(int i=0;i<matrix.length;++i){
for(int j=0;j<matrix[i].length;++j){
ans.set(i,j,matrix[i][j]-m.get(i,j));
}
}
return ans;
}
Matrix multiply(Matrix m){
if(size().width!=m.size().height){
throw new IllegalArgumentException("matrix length is not same");
}
Matrix ans=new Matrix(size().height,m.size().width);
Dimension size=ans.size();
int len=size().width;
for(int i=0;i<size.height;++i){
for(int j=0;j<size.width;++j){
long sum=0;
for(int k=0;k<len;++k){
sum += matrix[i][k]*m.get(k,j);
}
ans.set(i,j,sum);
}
}
return ans;
}
Matrix modAdd(Matrix m,long mod){
if(!size().equals(m.size())){
throw new IllegalArgumentException("matrix size is not same");
}
Matrix ans=new Matrix(size(),0);
for(int i=0;i<matrix.length;++i){
for(int j=0;j<matrix[i].length;++j){
ans.set(i,j,MathFunction.remainder(matrix[i][j]+m.get(i,j),mod));
}
}
return ans;
}
Matrix modSubtract(Matrix m,long mod){
if(!size().equals(m.size())){
throw new IllegalArgumentException("matrix size is not same");
}
Matrix ans=new Matrix(size(),0);
for(int i=0;i<matrix.length;++i){
for(int j=0;j<matrix[i].length;++j){
ans.set(i,j,MathFunction.remainder(matrix[i][j]-m.get(i,j),mod));
}
}
return ans;
}
Matrix modMultiply(Matrix m,long mod){
if(size().width!=m.size().height){
throw new IllegalArgumentException("matrix length is not same");
}
Matrix ans=new Matrix(size().height,m.size().width);
Dimension size=ans.size();
int len=size().width;
for(int i=0;i<size.height;++i){
for(int j=0;j<size.width;++j){
long sum=0;
for(int k=0;k<len;++k){
sum=MathFunction.remainder(sum+matrix[i][k]*m.get(k,j),mod);
}
ans.set(i,j,sum);
}
}
return ans;
}
static Matrix pow(Matrix original,Matrix pw,long exp){
Matrix a=original.copy();
Matrix b=pw.copy();
while(0<exp){
if((exp&1)==1){
a=b.multiply(a);
}
b=b.multiply(b);
exp >>= 1;
}
return a;
}
static Matrix modPow(Matrix original,Matrix pw,long exp,long mod){
Matrix a=original.copy();
Matrix b=pw.copy();
while(0<exp){
if((exp&1)==1){
a=b.modMultiply(a,mod);
}
b=b.modMultiply(b,mod);
exp >>= 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<N;i++){
System.arraycopy(mat[i],0,internalMatrix[i],0,N);
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(i<j){
long buf=internalMatrix[j][i]*MathFunction.modPow(internalMatrix[i][i],mod-2,mod)%mod;
for(int k=0;k<N;k++){
internalMatrix[j][k]-=internalMatrix[i][k]*buf%mod;
if(internalMatrix[j][k]<0){
internalMatrix[j][k]+=mod;
}
}
}
}
}
long det=1;
for(int i=0;i<N;i++){
det*=internalMatrix[i][i];
det%=mod;
}
return det;
}
static long determinant(long[][] mat){
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];
}
int N=mat.length;
RationalNumber[][] internalMatrix=new RationalNumber[N][N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
internalMatrix[i][j]=RationalNumber.valueOf(mat[i][j]);
}
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(i<j){
RationalNumber buf=internalMatrix[j][i].divide(internalMatrix[i][i]);
for(int k=0;k<N;k++){
internalMatrix[j][k]=internalMatrix[j][k].subtract(internalMatrix[i][k].multiply(buf));
}
}
}
}
RationalNumber det=RationalNumber.ONE;
for(int i=0;i<N;i++){
det=det.multiply(internalMatrix[i][i]);
}
return det.longValue();
}
@Override public String toString(){
StringBuilder ans=new StringBuilder();
ans.append(Arrays.toString(matrix[0]));
for(int i=1;i<matrix.length;++i){
ans.append("\n");
ans.append(Arrays.toString(matrix[i]));
}
return ans.toString();
}
}
class RationalNumber extends Number implements Comparable<RationalNumber>, 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;i<n;++i)ans[i]=nextByte();return ans;}
int[]nextInt(int n){var ans=new int[n];for(int i=0;i<n;++i)ans[i]=nextInt();return ans;}
long[]nextLong(int n){var ans=new long[n];for(int i=0;i<n;++i)ans[i]=nextLong();return ans;}
String[]next(int n){var ans=new String[n];for(int i=0;i<n;++i)ans[i]=next();return ans;}
byte[][]nextByte(int n,int m){var ans=new byte[n][];for(int i=0;i<n;++i)ans[i]=nextByte(m);return ans;}
int[][]nextInt(int n,int m){var ans=new int[n][];for(int i=0;i<n;++i)ans[i]=nextInt(m);return ans;}
long[][]nextLong(int n,int m){var ans=new long[n][];for(int i=0;i<n;++i)ans[i]=nextLong(m);return ans;}
String[][]next(int n,int m){var ans=new String[n][];for(int i=0;i<n;++i)ans[i]=next(m);return ans;}
char[]nextCharArray(){return next().toCharArray();}
char[][]nextCharArray(int n){var ans=new char[n][];for(int i=0;i<n;++i)ans[i]=nextCharArray();return ans;}
int[][]nextGraph(int N,int M){if(M==0)return new int[N+1][0];var ans=new int[N+1][];var count=new int[N+1];var path=nextInt(M,2);for(var temp:path){++count[temp[0]];++count[temp[1]];}for(int i=1;i<=N;++i)ans[i]=new int[count[i]];for(var temp:path){ans[temp[0]][--count[temp[0]]]=temp[1];ans[temp[1]][--count[temp[1]]]=temp[0];}ans[0]=new int[0];return ans;}
Point nextPoint(){return new Point(nextInt(),nextInt());}
Point[]nextPoint(int n){var ans=new Point[n];for(int i=0;i<n;++i)ans[i]=nextPoint();return ans;}
void close(){try{is.close();}catch(IOException e){e.printStackTrace();System.exit(1);}}
}
class SimpleWriter implements Closeable,Flushable,AutoCloseable{
boolean autoFlush;
SimpleOutputStream out;
static char[]charsOfReturn;
static byte[]integerBuffer,MIN_VALUE_ARRAY;
static byte ZERO;
static{charsOfReturn=System.lineSeparator().toCharArray();integerBuffer=new byte[20];integerBuffer[0]='-';ZERO='0';MIN_VALUE_ARRAY=new byte[]{'-','9','2','2','3','3','7','2','0','3','6','8','5','4','7','7','5','8','0','8'};}
SimpleWriter(OutputStream out){this(out,false);}
SimpleWriter(OutputStream out,boolean autoFlush){this.out=new SimpleOutputStream(out,1<<17);this.autoFlush=autoFlush;}
public void flush(){try{out.flush();}catch(Exception x){x.printStackTrace();System.exit(1);}}
public void close(){try{if(out==null)return;out.close();out=null;}catch(Exception x){x.printStackTrace();System.exit(1);}}
void write(int c){try{out.write(c);}catch(Exception x){x.printStackTrace();System.exit(1);}}
void write(char[]buf,int off,int len){try{out.write(buf,off,len);}catch(Exception x){x.printStackTrace();System.exit(1);}}
void write(byte[]buf,int off,int len){try{out.write(buf,off,len);}catch(Exception x){x.printStackTrace();System.exit(1);}}
void write(char[]buf){write(buf,0,buf.length);}
void write(byte[]buf){write(buf,0,buf.length);}
void write(String s,int off,int len){try{out.write(s.toCharArray(),off,len);}catch(Exception x){x.printStackTrace();System.exit(1);}}
void write(String s){write(s.toCharArray(),0,s.length());}
void newLine(){try{out.write(charsOfReturn,0,charsOfReturn.length);if(autoFlush)out.flush();}catch(Exception x){x.printStackTrace();System.exit(1);}}
void print(boolean b){write(b?"true":"false");}
void print(char c){write(c);}
void print(long l){if(l==Long.MIN_VALUE)write(MIN_VALUE_ARRAY);else{long num=Math.abs(l);int len=MathFunction.digit(num);for(int i=len;i>0;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;i<array.length;++i){print(str);print(array[i]);}}
void print(int[]array,char c){if(array.length==0)return;print(array[0]);for(int i=1;i<array.length;++i){print(c);print(array[i]);}}
void print(int[][]array){print(array,' ');}
void print(int[][]arrays,String str){if(arrays.length==0)return;print(arrays[0],str);for(int i=1;i<arrays.length;++i){println();print(arrays[i],str);}}
void print(int[][]arrays,char c){if(arrays.length==0)return;print(arrays[0],c);for(int i=1;i<arrays.length;++i){println();print(arrays[i],c);}}
void println(int[]array){print(array,' ');println();}
void println(int[]array,String str){print(array,str);println();}
void println(int[]array,char c){print(array,c);println();}
void println(int[][]array){print(array,' ');println();}
void println(int[][]arrays,String str){print(arrays,str);println();}
void println(int[][]arrays,char c){print(arrays,c);println();}
void print(long[]array){print(array,' ');}
void print(long[]array,String str){if(array.length==0)return;print(array[0]);for(int i=1;i<array.length;++i){print(str);print(array[i]);}}
void print(long[]array,char c){if(array.length==0)return;print(array[0]);for(int i=1;i<array.length;++i){print(c);print(array[i]);}}
void print(long[][]array){print(array,' ');}
void print(long[][]arrays,String str){if(arrays.length==0)return;print(arrays[0],str);for(int i=1;i<arrays.length;++i){println();print(arrays[i],str);}}
void print(long[][]arrays,char c){if(arrays.length==0)return;print(arrays[0],c);for(int i=1;i<arrays.length;++i){println();print(arrays[i],c);}}
void println(long[]array){println(array,' ');}
void println(long[]array,String str){print(array,str);println();}
void println(long[]array,char c){print(array,c);println();}
void println(long[][]array){println(array,' ');}
void println(long[][]arrays,String str){print(arrays,str);println();}
void println(long[][]arrays,char c){print(arrays,c);println();}
void print(double[]array){print(array,' ');}
void print(double[]array,String str){print(array[0]);for(int i=1;i<array.length;++i){print(str);print(array[i]);}}
void print(double[]array,char c){print(array[0]);for(int i=1;i<array.length;++i){print(c);print(array[i]);}}
void print(double[][]array){print(array,' ');}
void print(double[][]arrays,String str){print(arrays[0],str);for(int i=1;i<arrays.length;++i){println();print(arrays[i],str);}}
void print(double[][]arrays,char c){print(arrays[0],c);for(int i=1;i<arrays.length;++i){println();print(arrays[i],c);}}
void println(double[]array){println(array,' ');}
void println(double[]array,String str){print(array,str);println();}
void println(double[]array,char c){print(array,c);println();}
void println(double[][]array){println(array,' ');}
void println(double[][]arrays,String str){print(arrays,str);println();}
void println(double[][]arrays,char c){print(arrays,c);println();}
void println(char[]cs,String str){print(cs[0]);for(int i=1;i<cs.length;++i){print(str);print(cs[i]);}println();}
void println(char[]cs,char c){print(cs[0]);for(int i=1;i<cs.length;++i){print(c);print(cs[i]);}println();}
void println(char[][]cs){for(char[]c:cs)println(c);}
void println(char[][]cs,String str){for(char[]c:cs)println(c,str);}
void println(char[][]cs,char c){for(char[]cc:cs)println(cc,c);}
<E>void print(E[]array){print(array,' ');}
<E>void print(E[]array,String str){print(array[0]);for(int i=1;i<array.length;++i){print(str);print(array[i]);}}
<E>void print(E[]array,char c){print(array[0]);for(int i=1;i<array.length;++i){print(c);print(array[i]);}}
<E>void print(E[][]arrays){print(arrays,' ');}
<E>void print(E[][]arrays,String str){print(arrays[0],str);for(int i=1;i<arrays.length;++i){println();print(arrays[i],str);}}
<E>void print(E[][]arrays,char c){print(arrays[0],c);for(int i=1;i<arrays.length;++i){println();print(arrays[i],c);}}
<E>void println(E[]array){println(array,' ');}
<E>void println(E[]array,String str){print(array,str);println();}
<E>void println(E[]array,char c){print(array,c);println();}
<E>void println(E[][]arrays){println(arrays,' ');}
<E>void println(E[][]arrays,String str){print(arrays,str);println();}
<E>void println(E[][]arrays,char c){print(arrays,c);println();}
<E>void println(List<E>list){println(list,' ');}
<E>void println(List<E>list,String str){if(list.size()>0){print(list.get(0));for(int i=1;i<list.size();++i){print(str);print(list.get(i));}}println();}
<E>void println(List<E>list,char c){if(list.size()>0){print(list.get(0));for(int i=1;i<list.size();++i){print(c);print(list.get(i));}}println();}
class SimpleOutputStream{
byte[] buf;
int count;
OutputStream out;
SimpleOutputStream(OutputStream out,int size){this.out=out;if(size<=0)throw new IllegalArgumentException("Buffer size <= 0");buf=new byte[size];}
void flushBuffer()throws IOException{if(count>0){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<len;i++)buf[count+i]=(byte)ch[i+off];count+=len;}
byte[]parseByteArray(char[]ch,int off,int len){var ans=new byte[len];for(int i=0;i<len;i++)ans[i]=(byte)ch[i+off];return ans;}
void write(byte[]b,int off,int len)throws IOException{if(len>=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;}
}
}