import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Comparator; import java.util.HashSet; import java.util.List; import java.util.NoSuchElementException; import java.util.Set; //@Japanese /* PriorityQueueは拡張for文で出すとsortされてない順番で出てくる * longのbit演算は1L< dt = new ArrayList<>(); Graph(int sz) { for(int i = 0; i < sz; i++) { Node node1 = new Node(); dt.add(node1); } } public void add(int v8, int cnct2, int w) { dt.get(v8).add(new Edge(v8, cnct2, w)); } public void add2(int v1, int v2, int w) { dt.get(v1).add(new Edge(v1, v2, w)); dt.get(v2).add(new Edge(v2, v1, w)); } public Set get(int v) { return dt.get(v).getAll(); } public int size() { return dt.size(); } public int sizeOf(int v) { return dt.get(v).size(); } public void clear() { for(int i = 0; i < dt.size(); i++) { dt.get(i).clear(); } } public void clear(int v) { dt.get(v).clear(); } private void add_v(Node v_new) { dt.add(v_new); } public void show2() { for (int i = 0; i < dt.size(); i++) { System.out.print(i+":"); for(Edge e: dt.get(i).getAll()) { e.show2(); } System.out.println(); } } public static Graph make_Graph(int vn, int en, FastScanner sc) { Graph g = new Graph(vn); for(int i = 0; i < en; i++) { int s1 = sc.nexI() - 1; int g1 = sc.nexI() - 1; int w = sc.nexI(); g.add2(s1, g1, w); } return g; } } static class Node { // 重みつきグラフの頂点 private Set next_vs = new HashSet<>(); public void add(Edge cnct2) { next_vs.add(cnct2); } public Set getAll() { return next_vs; } public int size() { return next_vs.size(); } public void clear() { next_vs.clear(); } public void addAll(Node list2add) { this.next_vs.addAll(list2add.next_vs); } } static class Edge { //重み着きのグラフの辺 int from=-1, v2=-1; int w; public Edge(int going2, int weight_route) { this.v2 = going2; this.w = weight_route; } public Edge(int come8, int going2, int weight_route) { this.from = come8; this.v2 = going2; this.w = weight_route; } public void show2() { System.out.println(this.from +"->"+this.v2+" :w="+this.w); } } static class CompEdge_float implements Comparator{ //今は小さいのが前に出てくる public int compare(Edge a, Edge b) { if(a.w>b.w) return 1; else if(a.w=0) ? a: -a; } private static long abs(long a) { return (a>=0) ? a: -a; } private static double abs(double a) { return (a>=0.0) ? a: -a; } private static int min(int a, int b) { return (a>b) ? b : a; } private static long min(long a, long b) { return (a>b) ? b : a; } private static double min(double a, double b) { return (a>b) ? b : a; } private static int max(int a, int b) { return (a>b) ? a : b; } private static long max(long a, long b) { return (a>b) ? a : b; } private static double max(double a, double b) { return (a>b) ? a : b; } private static int pow2(int num2pow) { return num2pow*num2pow; } private static long pow2(long num2pow) { return num2pow*num2pow; } private static int pow(int num_powered, int index) { int ans = 1; for(int i=0; i=0); } return ans; } private static long pow(long num_powered, int index) { long ans = 1L; for(int i=0; i=0L); } return ans; } private static long powP(long num_powered, long index, long p) { //@Japanese 繰り返し二乗法 if(num_powered==0L) return 0L; if(index==0L) return 1L; if(index==2L) { long ans = num_powered*num_powered; assertion(ans>0); return ans%p; } int d = getDigit2(index); long[] num_done_by2 = new long[d+1]; num_done_by2[0] = num_powered; for(int i=1; i<=d; i++) { num_done_by2[i] = num_done_by2[i-1]*num_done_by2[i-1]; assertion(num_done_by2[i]>0); num_done_by2[i]%=p; } long ans=1L; for(int i=d; i>=0; i--) { if(index >= (1L<<(long)i)) { index -= (1L<<(long)i); ans = ans*num_done_by2[i]; assertion(ans>0); ans %= p; } } return ans%p; } private static double hypod(double a, double b) { return Math.sqrt(a*a+b*b); } private static int getDigit2(long num2know) { long compare4 = 1L; int digit = 0; while(num2know > compare4) { digit ++; compare4 = (1L<<(long)digit); } return digit; //num <= 2^digit } private static int getDigit10(long num2know) { long compare4 = 1L; int digit = 0; while(num2know >= compare4) { digit ++; compare4 *= 10L; } return digit; //@Japanese num は digit桁の数で、10^digit未満 } private static int divceil(int numerator, int denominator) { return (numerator+denominator-1)/denominator; } private static long divceil(long numerator, long denominator) { return (numerator+denominator-1L)/denominator; } private static long factorial(int n) { long ans=1L; for(long i=n; i>0; i--) { ans *= i; assertion(ans>=0L); } return ans; } private static long facP(int n, long p) { long ans=1L; for(long i=n; i>0; i--) { ans *= i; ans %= p; } return ans; } private static long lcm(long m, long n) { assertion((m>0L) && (n>0L)); long ans = m/gcd(m,n); ans *= n; return ans; } private static long gcd(long m, long n) { //if(isINFL(-m)) return n; assertion((m>=0L) && (n>=0L)); if(m < n) return gcd(n, m); if(n == 0) return m; return gcd(n, m % n); } private static boolean is_prime(long n2check) { if(n2check==1L) return false; for(long i=2L; i<=Math.sqrt(n2check); i++) { if(n2check%i == 0) return false; } return true; } private static long modinv(long n, long p) { assertion((n>0L)&&(p>1L)&&(gcd(n,p)==1L)); n %= p; //@Japanese //a⊥p, >1に注意 //yn≡1(mod p) //<-> xp+yn=1; (n1) { long quo = a/b; long rem = a%b; a=b; b=rem; long s2 = s*quo+u, t2=t*quo+v; u=s; v=t; s=s2; t=t2; } long det = s*v-t*u; assertion(abs(det)==1); s /= det; s %= p; if(s < 0L) s += p; return s; } private static int minAll(int[] dt4min) { int min = INF; for(int element: dt4min) { if(element < min) min = element; } return min; } private static long minAll(long[] dt4min) { long min = INFL; for(long element: dt4min) { if(element < min) min = element; } return min; } private static int maxAll(int[] dt4max) { int max = -INF; for(int element: dt4max) { if(element < max) max = element; } return max; } private static long maxAll(long[] dt4max) { long max = -INFL; for(long element: dt4max) { if(element < max) max = element; } return max; } private static int sumAll(int[] dt4sum) { int sum_of_dt = 0; for(int element: dt4sum) { sum_of_dt += element; } return sum_of_dt; } private static long sumAll(long[] dt4sum) { long sum_of_dt = 0L; for(long element: dt4sum) { sum_of_dt += element; } return sum_of_dt; } private static int sumAll(ArrayList dt4sum) { int sum_of_dt = 0; for(long element: dt4sum) { sum_of_dt += element; } return sum_of_dt; } /*private static long sumAll(ArrayList dt4sum) { long sum_of_dt = 0L; for(long element: dt4sum) { sum_of_dt += element; } return sum_of_dt; }*/ private static int[] reverse(int[] as) { int ln = as.length; int[] bs = new int[ln]; for(int i=0; i= height) return false; if(x >= width) return false; return true; } private static boolean is_in_area(Vector v, int height, int width) { if(v.y < 0) return false; if(v.x < 0) return false; if(v.y >= height) return false; if(v.x >= width) return false; return true; } private static int nC2(int n) { return ((n*(n-1))/2); } private static long nC2(long n) { return ((n*(n-1L))/2L); } private static int iflag(int pos) { assertion(pos<31); return (1< 0) return true; else return false; } private static boolean isFlaged(long bit, int pos) { if((bit&(1L<<(long)pos)) > 0L) return true; else return false; } private static int deflag(int bit, int pos) { return bit&~(1< 0) ans++; } return ans; } private static int countFlaged(long bit) { int ans=0; for(long i=0; i<63L; i++) { if((bit&(1L< 0) ans++; } return ans; } private static int[] Xdir4 = {1,0,0,-1}; private static int[] Ydir4 = {0,1,-1,0}; private static int[] Xdir8 = {1,1,1,0,0,-1,-1,-1}; private static int[] Ydir8 = {1,0,-1,1,-1,1,0,-1}; public static int biSearch(int[] dt, int target) { int left=0, right=dt.length-1; int mid=-1; while(left<=right) { mid = (right+left)/2; if(dt[mid] == target) return mid; if(dt[mid] < target) left=mid+1; else right=mid-1; } return -1; } public static int biSearchMax(long[] dt, long target) { int left=-1, right=dt.length, mid=-1; while((right-left)>1) { mid = (right+left)/2; if(dt[mid] <= target) left=mid; else right=mid; } return left; //@Japanese target以下の最大のaddress } public static int biSearchMin(long[] dt, long target) { int left=-1, right=dt.length, mid=-1; while((right-left)>1) { mid = (right+left)/2; if(dt[mid] <= target) left=mid; else right=mid; } return right; //@Japanese targetより大きい最小のaddress } private static void fill(boolean[] target, boolean reset) { for(int i=0; i dt) { long element=0; while(dt.size()>0) { element=dt.removeFirst(); System.out.print(element); } System.out.println("\n"); } static void show2(List dt) { for(int i=0; i array) { PrintWriter out = new PrintWriter(System.out); for(int i=0; i array) { PrintWriter out = new PrintWriter(System.out); out.print(array.get(0)); for(int i=1; i Integer.MAX_VALUE) { throw new NumberFormatException(); } return (int) nl; } public double nexD() { return Double.parseDouble(next());} //a means array public void ai(int[]... array) { for(int i=0; i