結果
問題 | No.2569 はじめてのおつかいHard |
ユーザー |
|
提出日時 | 2023-12-02 16:32:59 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 710 ms / 2,000 ms |
コード長 | 40,724 bytes |
コンパイル時間 | 5,726 ms |
コンパイル使用メモリ | 103,168 KB |
実行使用メモリ | 93,140 KB |
最終ジャッジ日時 | 2024-09-26 20:25:18 |
合計ジャッジ時間 | 11,573 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 |
ソースコード
import java.awt.Point;import java.io.*;import java.math.BigInteger;import java.nio.charset.*;import java.util.*;import java.util.function.*;class Main{static boolean autoFlush = false;static SimpleScanner sc = new SimpleScanner(System.in);static SimpleWriter out = new SimpleWriter(System.out,autoFlush);public static void main(String[] args){int N = sc.nextInt();int M = sc.nextInt();ArrayList<ArrayList<int[]>> list = new ArrayList<>();ArrayList<ArrayList<int[]>> rlist = new ArrayList<>();for(int i=0;i<=N;i++){list.add(new ArrayList<>());rlist.add(new ArrayList<>());}while(M-->0){int u = sc.nextInt();int v = sc.nextInt();int t = sc.nextInt();list.get(u).add(new int[]{v,t});rlist.get(v).add(new int[]{u,t});}record Node(int now,long cost,boolean f){};PriorityQueue<Node> queue = new PriorityQueue<>((a,b)->Long.compare(a.cost,b.cost));long[] dist = new long[2*N+1];Arrays.fill(dist,Long.MAX_VALUE>>1);dist[N] = 0;queue.add(new Node(N,0,false));while(queue.size()>0){Node n = queue.poll();if(dist[n.now+(n.f?N:0)]<n.cost)continue;for(int[] path:list.get(n.now)){boolean flag = n.f||path[0]==N-1;if(dist[n.now+(n.f?N:0)]+path[1]<dist[path[0]+(flag?N:0)]){dist[path[0]+(flag?N:0)] = dist[n.now+(n.f?N:0)]+path[1];queue.add(new Node(path[0],dist[path[0]+(flag?N:0)],flag));}}}long[] rdist = new long[2*N+1];Arrays.fill(rdist,Long.MAX_VALUE>>1);rdist[N] = 0;queue.add(new Node(N,0,false));while(queue.size()>0){Node n = queue.poll();if(rdist[n.now+(n.f?N:0)]<n.cost)continue;for(int[] path:rlist.get(n.now)){boolean flag = n.f||path[0]==N-1;if(rdist[n.now+(n.f?N:0)]+path[1]<rdist[path[0]+(flag?N:0)]){rdist[path[0]+(flag?N:0)] = rdist[n.now+(n.f?N:0)]+path[1];queue.add(new Node(path[0],rdist[path[0]+(flag?N:0)],flag));}}}long max = Long.MAX_VALUE>>1;for(int i=1;i<N-1;i++){long ans1 = dist[i]+rdist[N+i];long ans2 = dist[N+i]+rdist[i];long ans = Math.min(ans1,ans2);out.println(max<=ans?-1:ans);}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 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 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;}}int temp = array[index1];array[index1] = array[index2];array[index2] = temp;Arrays.sort(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;}}long temp = array[index1];array[index1] = array[index2];array[index2] = temp;Arrays.sort(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;}}char temp = array[index1];array[index1] = array[index2];array[index2] = temp;Arrays.sort(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 = -1;E min = null;int subIndex = -1;E max = array[index1];for(int i = index1+1;i<array.length;++i){if(min==null||MathFunction.rangeCheckOpen(array[i],array[index1],min)){min = array[i];index2 = i;}if(max.compareTo(array[i])<0){subIndex = i;max = array[i];}}E temp;if(index2==-1){temp = array[subIndex];array[subIndex] = array[index1];}else{temp = array[index2];array[index2] = array[index1];}array[index1] = temp;Arrays.sort(array,index1+1,array.length);return true;}}class Converter{static String reverse(String str){StringBuilder sb = new StringBuilder();for(int i = str.length()-1;i>=0;--i)sb.append(str.charAt(i));return sb.toString();}}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);for(int i=2;i<=limit;++i)if(numbers.get(i))for(int j=i*i;j<=num;j+=i)if(numbers.get(j))numbers.clear(j);int[] answer = new int[numbers.cardinality()];int i = 2, index = 0;do{i = numbers.nextSetBit(i);answer[index++] = i++;}while(index!=answer.length);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 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<=l.compareTo(num)&&0<num.compareTo(r);}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<l.compareTo(num)&&0<num.compareTo(r);}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<=l.compareTo(num)&&0<=num.compareTo(r);}}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;elsea = (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;elsea = (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;elsea = (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;elsea = (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;elsea = (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;elsea = (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;elsea = (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;elsea = (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;elsea = (ans=c);}return ans;}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;elsea = 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;elsea = 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;elsea = 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;elsea = 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;elsea = 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;elsea = 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;elsea = 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;elsea = 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;elsea = (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;elsea = (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;elsea = (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;elsea = (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;elsea = (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;elsea = (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;elsea = (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;elsea = (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;elsea = 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;elsea = 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;elsea = 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;elsea = 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;elsea = 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;elsea = 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;elsea = 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;elsea = c+1;}return ans;}}class BIT{int size;long[] tree;BIT(int n){size = n;tree = new long[n+1];}long sum(int i){long sum = 0;while(i>0){sum += tree[i];i ^= i&(-i);}return sum;}void add(int i,long x){while(i<=size){tree[i] += x;i += i&(-i);}}void clear(){Arrays.fill(tree,0L);}}class RollingHash implements Comparable<RollingHash>{static long BASE = new Random().nextInt(1000)+Character.MAX_VALUE+1;static long MASK30 = (1L<<30)-1;static long MASK31 = (1L<<31)-1;static long MOD = (1L<<61)-1;static long 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;long ad = a&MASK31;long bu = b>>31;long bd = b&MASK31;long mid = ad*bu+au*bd;long midu = mid>>30;long midd = mid&MASK30;return mod(au*bu*2+midu+(midd<<31)+ad*bd);}static long mod(long x){long xu = x>>61;long xd = x&MASK61;long 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;long 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){if(r1-l1!=r2-l2)return false;return getHash(l1,r1)==rh.getHash(l2,r2);}int length(){return string.length();}public int hashCode(){return string.hashCode();}public String toString(){return string;}public boolean equals(Object o){if(o instanceof RollingHash rh)return equals(rh,0,length(),0,rh.length());return false;}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){long 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);}}@SuppressWarnings("unchecked") abstract class SegmentTree<E>{int N, size;E def;Object[] node;SegmentTree(int n,E def,boolean include){int num = 2;while(num<n<<1)num <<= 1;N = num;size = num>>1-(include?1:0);node = new Object[N];this.def = def;Arrays.fill(node,this.def);}SegmentTree(E[] arr,E def,boolean include){int num = 2;while(num<arr.length<<1)num <<= 1;N = num;size = num>>1-(include?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);}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){if(par[ind]==-1)return ind;elsereturn 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;InputStream is;byte[] buff;int point, length;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(){byte c = read();while(c<=' ')c = read();return c;}int nextInt(){int ans = 0;byte c = nextByte();boolean 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;byte c = nextByte();boolean 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(){StringBuilder ans = new StringBuilder();byte c = nextByte();while(c>' '){ans.append((char)c);c = read();}return ans.toString();}BigInteger nextBigInteger(){return new BigInteger(next());}byte[] nextByte(int n){byte[] ans = new byte[n];for(int i = 0;i<n;++i)ans[i] = nextByte();return ans;}int[] nextInt(int n){int[] ans = new int[n];for(int i = 0;i<n;++i)ans[i] = nextInt();return ans;}long[] nextLong(int n){long[] ans = new long[n];for(int i = 0;i<n;++i)ans[i] = nextLong();return ans;}String[] next(int n){String[] ans = new String[n];for(int i = 0;i<n;++i)ans[i] = next();return ans;}byte[][] nextByte(int n,int m){byte[][] ans = new byte[n][];for(int i = 0;i<n;++i)ans[i] = nextByte(m);return ans;}int[][] nextInt(int n,int m){int[][] ans = new int[n][];for(int i = 0;i<n;++i)ans[i] = nextInt(m);return ans;}long[][] nextLong(int n,int m){long[][] ans = new long[n][];for(int i = 0;i<n;++i)ans[i] = nextLong(m);return ans;}String[][] next(int n,int m){String[][] 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){char[][] 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];int[][] ans = new int[N+1][];int[] count = new int[N+1];int[][] path = nextInt(M,2);for(int[] temp: path){++count[temp[0]];++count[temp[1]];}for(int i = 1;i<=N;++i)ans[i] = new int[count[i]];for(int[] 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){Point[] ans = new Point[n];for(int i = 0;i<n;++i)ans[i] = nextPoint();return ans;}public void close(){try{is.close();}catch(IOException e){e.printStackTrace();System.exit(1);}}}class SimpleOutputStream extends FilterOutputStream{byte[] buf;int count;SimpleOutputStream(OutputStream out){this(out,1<<17);}SimpleOutputStream(OutputStream out,int size){super(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;}}public void write(int b) throws IOException{if(count>=buf.length)flushBuffer();buf[count++] = (byte)b;}public 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;}public void flush() throws IOException{flushBuffer();out.flush();}}class SimpleWriter implements Appendable, Closeable, Flushable, AutoCloseable{Writer out;boolean autoFlush;boolean trouble = false;Formatter formatter;PrintStream psOut = null;static Charset toCharset(String csn){if(csn==null)throw new NullPointerException("charsetName");try{return Charset.forName(csn);}catch(IllegalCharsetNameException|UnsupportedCharsetException e){e.printStackTrace();System.exit(1);return null;}}SimpleWriter(Writer out){this(out,false);}SimpleWriter(Writer out,boolean autoFlush){this.out = out;this.autoFlush = autoFlush;}SimpleWriter(OutputStream out){this(out,false);}SimpleWriter(OutputStream out,boolean autoFlush){this(out,autoFlush,Charset.defaultCharset());}SimpleWriter(OutputStream out,boolean autoFlush,Charset charset){this(new BufferedWriter(new OutputStreamWriter(new SimpleOutputStream(out),charset)),autoFlush);if(out instanceof PrintStream)psOut = (PrintStream)out;}void ensureOpen() throws IOException{if(out==null)throw new IOException("Stream closed");}public void flush(){try{ensureOpen();out.flush();}catch(IOException x){trouble = true;}}public void close(){try{if(out==null)return;out.close();out = null;}catch(IOException x){trouble = true;}}boolean checkError(){if(out!=null)flush();else if(psOut!=null)return psOut.checkError();return trouble;}void setError(){trouble = true;}void clearError(){trouble = false;}void write(int c){try{ensureOpen();out.write(c);}catch(InterruptedIOException x){Thread.currentThread().interrupt();}catch(IOException x){trouble = true;}}void write(char[] buf,int off,int len){try{ensureOpen();out.write(buf,off,len);}catch(InterruptedIOException x){Thread.currentThread().interrupt();}catch(IOException x){trouble = true;}}void write(char[] buf){write(buf,0,buf.length);}void write(String s,int off,int len){try{ensureOpen();out.write(s,off,len);}catch(InterruptedIOException x){Thread.currentThread().interrupt();}catch(IOException x){trouble = true;}}void write(String s){write(s,0,s.length());}void newLine(){try{ensureOpen();out.write(System.lineSeparator());if(autoFlush)out.flush();}catch(InterruptedIOException x){Thread.currentThread().interrupt();}catch(IOException x){trouble = true;}}void print(boolean b){write(b?"true":"false");}void print(char c){write(c);}void print(int i){write(String.valueOf(i));}void print(long l){write(String.valueOf(l));}void print(float f){write(String.valueOf(f));}void print(double d){write(String.valueOf(d));}void print(char[] s){write(s);}void print(String s){write(s);}void print(Object obj){write(obj.toString());}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.toString());println();}SimpleWriter printf(String format,Object... args){return format(format,args);}SimpleWriter printf(Locale l,String format,Object... args){return format(l,format,args);}SimpleWriter format(String format,Object... args){try{ensureOpen();if((formatter==null)||(formatter.locale()!=Locale.getDefault()))formatter = new Formatter(this);formatter.format(Locale.getDefault(),format,args);if(autoFlush)out.flush();}catch(InterruptedIOException x){Thread.currentThread().interrupt();}catch(IOException x){trouble = true;}return this;}SimpleWriter format(Locale l,String format,Object... args){try{ensureOpen();if((formatter==null)||(formatter.locale()!=l))formatter = new Formatter(this,l);formatter.format(l,format,args);if(autoFlush)out.flush();}catch(InterruptedIOException x){Thread.currentThread().interrupt();}catch(IOException x){trouble = true;}return this;}public SimpleWriter append(CharSequence csq){write(String.valueOf(csq));return this;}public SimpleWriter append(CharSequence csq,int start,int end){if(csq==null)csq = "null";return append(csq.subSequence(start,end));}public SimpleWriter append(char c){write(c);return this;}void println(int[] array){println(array,' ');}void println(int[] array,String str){print(array[0]);for(int i = 1;i<array.length;++i){print(str);print(array[i]);}println();}void println(int[] array,char c){print(array[0]);for(int i = 1;i<array.length;++i){print(c);print(array[i]);}println();}void println(int[][] array){println(array,' ');}void println(int[][] arrays,String str){for(int[] array: arrays)println(array,str);}void println(int[][] arrays,char c){for(int[] array: arrays)println(array,c);}void println(long[] array){println(array,' ');}void println(long[] array,String str){print(array[0]);for(int i = 1;i<array.length;++i){print(str);print(array[i]);}println();}void println(long[] array,char c){print(array[0]);for(int i = 1;i<array.length;++i){print(c);print(array[i]);}println();}void println(long[][] array){println(array,' ');}void println(long[][] arrays,String str){for(long[] array: arrays)println(array,str);}void println(long[][] arrays,char c){for(long[] array: arrays)println(array,c);}void println(double[] array){println(array,' ');}void println(double[] array,String str){print(array[0]);for(int i = 1;i<array.length;++i){print(str);print(array[i]);}println();}void println(double[] array,char c){print(array[0]);for(int i = 1;i<array.length;++i){print(c);print(array[i]);}println();}void println(double[][] array){println(array,' ');}void println(double[][] arrays,String str){for(double[] array: arrays)println(array,str);}void println(double[][] arrays,char c){for(double[] array: arrays)println(array,c);}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 println(E[] array){println(array,' ');}<E> void println(E[] array,String str){print(array[0]);for(int i = 1;i<array.length;++i){print(str);print(array[i]);}println();}<E> void println(E[] array,char c){print(array[0]);for(int i = 1;i<array.length;++i){print(c);print(array[i]);}println();}<E> void println(E[][] arrays){println(arrays,' ');}<E> void println(E[][] arrays,String str){for(E[] array: arrays)println(array,str);}<E> void println(E[][] arrays,char c){for(E[] array: arrays)println(array,c);}<E> void println(List<E> list){println(list,' ');}<E> void println(List<E> list,String str){if(list.size()==0){println();return;}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){println();return;}print(list.get(0));for(int i = 1;i<list.size();++i){print(c);print(list.get(i));}println();}}