#977614 (Java21) No.2825 Sum of Scores of Sets of Specified Sections

提出ソース
結果

問題	No.2825 Sum of Scores of Sets of Specified Sections
ユーザー	viral8
提出日時	2024-04-27 11:19:55
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	63,403 bytes
コンパイル時間	4,431 ms
コンパイル使用メモリ	104,704 KB
実行使用メモリ	60,664 KB
最終ジャッジ日時	2024-07-26 20:02:08
合計ジャッジ時間	13,101 ms
ジャッジサーバーID （参考情報）	judge1 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	131 ms 54,900 KB
testcase_01	AC	585 ms 60,316 KB
testcase_02	AC	601 ms 60,664 KB
testcase_03	AC	585 ms 60,368 KB
testcase_04	AC	225 ms 55,276 KB
testcase_05	AC	165 ms 55,376 KB
testcase_06	WA	-
testcase_07	AC	182 ms 55,472 KB
testcase_08	AC	177 ms 55,492 KB
testcase_09	AC	148 ms 55,132 KB
testcase_10	AC	152 ms 55,064 KB
testcase_11	AC	136 ms 55,044 KB
testcase_12	AC	128 ms 54,872 KB
testcase_13	AC	151 ms 55,116 KB
testcase_14	AC	252 ms 55,544 KB
testcase_15	AC	254 ms 55,528 KB
testcase_16	AC	252 ms 55,488 KB
testcase_17	AC	247 ms 55,392 KB
testcase_18	AC	259 ms 55,496 KB
testcase_19	AC	259 ms 55,368 KB
testcase_20	AC	254 ms 55,320 KB
testcase_21	AC	252 ms 55,240 KB
testcase_22	AC	255 ms 55,328 KB
testcase_23	AC	248 ms 55,452 KB
testcase_24	AC	192 ms 55,296 KB
testcase_25	AC	188 ms 55,360 KB
testcase_26	AC	193 ms 55,516 KB
testcase_27	AC	194 ms 55,644 KB
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
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];
		}
		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;}
	}
}
yukicoder

結果

テストケース

ソースコード
