結果
| 問題 | No.2569 はじめてのおつかいHard |
| ユーザー |
 viral8
|
| 提出日時 | 2023-12-02 16:32:59 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 253 ms
55,808 KB |
| testcase_01 | AC | 264 ms
56,504 KB |
| testcase_02 | AC | 260 ms
55,448 KB |
| testcase_03 | AC | 261 ms
55,728 KB |
| testcase_04 | AC | 274 ms
56,588 KB |
| testcase_05 | AC | 662 ms
92,912 KB |
| testcase_06 | AC | 663 ms
65,928 KB |
| testcase_07 | AC | 578 ms
93,140 KB |
| testcase_08 | AC | 710 ms
91,820 KB |
| testcase_09 | AC | 442 ms
62,340 KB |
| testcase_10 | AC | 61 ms
37,268 KB |
| testcase_11 | AC | 61 ms
37,740 KB |
ソースコード
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;
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 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;
}
}
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;
else
return 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();
}
}