import java.awt.Dimension; import java.awt.Point; import java.io.*; import java.math.BigInteger; import java.util.*; import java.util.function.*; public 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.determinant()-1); out.close(); } } /*//////////////////////////////////////////////////////////////////////////////////////////// * My Library * @author viral *///////////////////////////////////////////////////////////////////////////////////////////// class Factorial{ long[]fact,inFact; long mod; Factorial(int N,long mod){fact=new long[N+1];fact[0]=fact[1]=1;for(int i=2;i<=N;++i)fact[i]=fact[i-1]*i%mod;inFact=new long[N+1];inFact[N]=MathFunction.modPow(fact[N],mod-2,mod);for(int i=N;i>0;--i)inFact[i-1]=inFact[i]*i%mod;inFact[0]=1;this.mod=mod;} long getFact(int num){return fact[num];} long getInFact(int num){return inFact[num];} long getInverse(int num){return fact[num-1]*inFact[num]%mod;} long getCombi(int a,int b){if(a<b||a<0||b<0)return 0;return (fact[a]*inFact[a-b]%mod)*inFact[b]%mod;} } 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); } static long determinant(long[][] mat){ if(mat.length==1){ return mat[0][0]; } long[][] miniMat=new long[mat.length-1][mat.length-1]; for(int i=1;i<mat.length;++i){ System.arraycopy(mat[i],1,miniMat[i-1],0,miniMat.length); } long ans=mat[0][0]*determinant(miniMat); for(int i=1;i<mat.length;++i){ for(int j=1;j<mat.length;++j){ miniMat[j-1][i-1]=mat[j][i-1]; } long num=mat[0][i]*determinant(miniMat); ans += i%2==0?num:-num; } return ans; } @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 RollingHash implements Comparable<RollingHash>{ static long BASE=new Random().nextInt(1000)+Character.MAX_VALUE+1,MASK30=(1L<<30)-1,MASK31=(1L<<31)-1,MOD=(1L<<61)-1,MASK61=MOD; long[]hash; String string; RollingHash(String str){string=str;hash=new long[str.length()+1];roll();} void roll(){int len=string.length();for(int i=1;i<=len;++i){hash[i]=multiply(hash[i-1],BASE)+string.charAt(i-1)-' '+1;if(MOD<=hash[i])hash[i]-=MOD;}} static long multiply(long a,long b){long au=a>>31,ad=a&MASK31,bu=b>>31,bd=b&MASK31,mid=ad*bu+au*bd,midu=mid>>30,midd=mid&MASK30;return mod(au*bu*2+midu+(midd<<31)+ad*bd);} static long mod(long x){long xu=x>>61,xd=x&MASK61,ans=xu+xd;if(MOD<=ans)ans-=MOD;return ans;} long getHash(int l,int r){return(hash[r]-multiply(hash[l],modBasePow(r-l))+MOD)%MOD;} static long modBasePow(long b){long ans=1,a=BASE;while(b>0){if((b&1)==1)ans=multiply(ans,a);a=multiply(a,a);b>>=1;}return ans;} boolean equals(RollingHash rh,int l1,int r1,int l2,int r2){return r1-l1!=r2-l2?false:getHash(l1,r1)==rh.getHash(l2,r2);} int length(){return string.length();} @Override public int hashCode(){return string.hashCode();} @Override public String toString(){return string;} @Override public boolean equals(Object o){return o instanceof RollingHash rh?equals(rh,0,length(),0,rh.length()):false;} @Override public int compareTo(RollingHash rh){return string.compareTo(rh.toString());} int compareTo(String str){return string.compareTo(str);} char charAt(int i){return string.charAt(i);} int compareToIgnoreCase(RollingHash rh){return string.compareToIgnoreCase(rh.toString());} int compareToIgnoreCase(String str){return string.compareToIgnoreCase(str);} void concat(RollingHash rh){concat(rh.toString());} void concat(String str){string=string.concat(str);hash=new long[string.length()+1];roll();} boolean contains(RollingHash rh){var hash=rh.getHash(0,rh.length());int len=length()-rh.length();for(int i=0;i<=len;++i)if(hash==getHash(i,rh.length()+i))return true;return false;} boolean contains(String str){return indexOf(str)!=-1;} int indexOf(int ch){return indexOf(ch,0);} int indexOf(int ch,int fromIndex){int len=length();for(int i=fromIndex;i<len;++i)if(string.charAt(i)==ch)return i;return -1;} int indexOf(String str){return indexOf(str,0);} int indexOf(String str,int fromIndex){long hash=0;for(char c: str.toCharArray()){hash=multiply(hash,BASE)+c-' '+1;if(MOD<=hash)hash-=MOD;}int len=length()-str.length();for(int i=fromIndex;i<=len;++i)if(hash==getHash(i,str.length()+i))return i;return -1;} boolean isEmpty(){return length()==0;} int lastIndexOf(int ch,int fromIndex){for(int i=fromIndex;i>=0;--i)if(string.charAt(i)==ch)return i;return -1;} int lastIndexOf(int ch){return lastIndexOf(ch,length()-1);} static RollingHash valueOf(boolean b){return new RollingHash(b?"true":"false");} static RollingHash valueOf(char c){return new RollingHash(""+c);} static RollingHash valueOf(char[] c){return new RollingHash(String.valueOf(c,0,c.length));} static RollingHash valueOf(char[] c,int offset,int count){return new RollingHash(String.valueOf(c,offset,count));} static RollingHash valueOf(double d){return new RollingHash(String.valueOf(d));} static RollingHash valueOf(float f){return new RollingHash(String.valueOf(f));} static RollingHash valueOf(int i){return new RollingHash(String.valueOf(i));} static RollingHash valueOf(long l){return new RollingHash(String.valueOf(l));} static RollingHash valueOf(Object obj){return new RollingHash(String.valueOf(obj));} } @SuppressWarnings("unchecked")abstract class SegmentTree<E>{ int N,size; E def; Object[]node; SegmentTree(int n,E def,boolean is1indexed){int num=2;while(num<n<<1)num<<=1;N=num;size=(num>>1)-(is1indexed?1:0);node=new Object[N];this.def=def;Arrays.fill(node,this.def);} SegmentTree(E[]arr,E def,boolean is1indexed){int num=2;while(num<arr.length<<1)num<<=1;N=num;size=num>>1-(is1indexed?1:0);node=new Object[N];this.def=def;System.arraycopy(arr,0,node,N>>1,arr.length);for(int i=arr.length+(N>>1);i<N;i++)node[i]=def;updateAll();} SegmentTree(int n,E def){this(n,def,false);} void updateAll(){for(int i=(N>>1)-1;i>0;i--)node[i]=function((E)node[i<<1],(E)node[(i<<1)+1]);} void update(int n,E value){n+=size;node[n]=value;n>>=1;while(n>0){node[n]=function((E)node[n<<1],(E)node[(n<<1)+1]);n>>=1;}} E get(int a){return(E)node[a+size];} E answer(){return(E)node[1];} E query(int l,int r){l+=size;r+=size;E answer=def;while(l>0&&r>0&&l<=r){if(l%2==1)answer=function((E)node[l++],answer);l>>=1;if(r%2==0)answer=function(answer,(E)node[r--]);r>>=1;}return answer;} abstract E function(E a,E b); } @SuppressWarnings("unchecked")abstract class LazySegmentTree<S,F>{ int size,log; S defaultS; F defaultF; S[]node; F[]lazy; LazySegmentTree(int N,S defaultS,F defaultF){this(N,defaultS,defaultF,false);} LazySegmentTree(int N,S defaultS,F defaultF,boolean is1indexed){this.log=32-Integer.numberOfLeadingZeros(N-1);this.size=(1<<log)-(is1indexed?1:0);this.defaultS=defaultS;this.defaultF=defaultF;this.node=(S[])new Object[1<<log+1];this.lazy=(F[])new Object[1<<log+1];clear();} LazySegmentTree(S[]defaultValues,S defaultS,F defaultF,boolean is1indexed){this(defaultValues.length,defaultS,defaultF,is1indexed);updateAll(defaultValues);} void clear(){Arrays.fill(this.node,this.defaultS);Arrays.fill(this.lazy,this.defaultF);} void updateAll(S[]defaultValues){System.arraycopy(defaultValues,0,node,1<<log,defaultValues.length);for(int i=(1<<log)-1;i>0;i--)node[i]=function(node[i<<1],node[i<<1|1]);} void spread(int index){if(lazy[index]!=defaultF){int l=index<<1,r=index<<1|1;node[l]=mapping(node[l],lazy[index]);node[r]=mapping(node[r],lazy[index]);lazy[l]=composition(lazy[l],lazy[index]);lazy[r]=composition(lazy[r],lazy[index]);lazy[index]=defaultF;}} void spreadLine(int from){for(int i=log;i>0;i--)spread(from>>i);} void spreadRange(int l,int r){for(int i=log;i>0;i--){if((l>>i<<i)!=l)spread(l>>i);if((r>>i<<i)!=r)spread(r>>i);}} void update(int index){while((index>>=1)>0)node[index]=function(node[index<<1],node[index<<1|1]);} void update(int l,int r){for(int i=1;i<=log;i++){int subL=l>>i,subR=r>>i;if((subL<<i)!=l)node[subL]=function(node[subL<<1],node[subL<<1|1]);if((subR<<i)!=r)node[subR]=function(node[subR<<1],node[subR<<1|1]);}} void update(int index,S x){index+=size;spreadLine(index);node[index]=x;update(index);} S get(int index){index+=size;spreadLine(index);return node[index];} S query(int l,int r){l+=size;r+=size;spreadRange(l,r);S sumL=defaultS,sumR=defaultS;while(l<r){if((l&1)==1)sumL=function(sumL,node[l++]);if((r&1)==1)sumR=function(node[--r],sumR);l>>=1;r>>=1;}return function(sumL,sumR);} S answer(){return node[1];} void apply(int index,F f){index+=size;spreadLine(index);node[index]=mapping(node[index],f);update(index);} void apply(int l,int r,F f){l+=size;r+=size;spreadRange(l,r);int subL=l,subR=r;while(subL<subR){if((subL&1)==1){node[subL]=mapping(node[subL],f);lazy[subL]=composition(lazy[subL++],f);}if((subR&1)==1){node[--subR]=mapping(node[subR],f);lazy[subR]=composition(lazy[subR],f);}subL>>=1;subR>>=1;}update(l,r);} abstract S function(S s1,S s2); abstract F composition(F f1,F f2); abstract S mapping(S s,F f); } class UnionFind{ int[]par,rank,size,path; int count; UnionFind(int N){count=N;par=new int[N];rank=new int[N];size=new int[N];path=new int[N];Arrays.fill(par,-1);Arrays.fill(size,1);} int root(int ind){return par[ind]==-1?ind:(par[ind]=root(par[ind]));} boolean isSame(int x,int y){return root(x)==root(y);} boolean unite(int x,int y){int rx=root(x);int ry=root(y);++path[rx];if(rx==ry)return false;if(rank[rx]<rank[ry]){int temp=rx;rx=ry;ry=temp;}par[ry]=rx;if(rank[rx]==rank[ry])++rank[rx];path[rx]+=path[ry];size[rx]+=size[ry];--count;return true;} int groupCount(){return count;} int pathCount(int x){return path[root(x)];} int size(int x){return size[root(x)];} } 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;} } }