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.List; import java.util.NoSuchElementException; public class Main { //PriorityQueueは拡張for文で出すとsortされてない順番で出てくる //longのbit演算は1L<{ //今は小さいのが前に出てくる public int compare(Edge a, Edge b) { if(a.wb.w) return -1; else return a.v2-b.v2; } } private static int INF = (int) 1e8; private static long INFL = (long) 1e17; private static long e97 = 1000000007L; private static void assertion(boolean should_true) { //should_trueがtrueでなければエラーを起こす。「断言」 if(!should_true) throw new AssertionError(); } private static int abs(int a) { return (a>=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) { //繰り返し二乗法 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 next = 0L; long[] num_done_by2 = new long[d+1]; num_done_by2[0] = num_powered; for(int i=1; i<=d; i++) { next = num_done_by2[i-1]*num_done_by2[i-1]; assertion(next>0); num_done_by2[i] = next%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^d以下 } private static int getDigit10(long num2know) { long compare4 = 1L; int digit = 0; while(num2know >= compare4) { digit ++; compare4 *= 10L; } return digit; //numはd桁の数で、10^dより小さい } 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)); //a⊥p, >1に注意 n %= p; //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; /*long b = p, u = 1L, v = 0L;//動作原理不明 while (b > 0) { long t = a / b; long pe = a%b; a = b; b = pe; pe = u-t*v; u = v; v = pe; }*/ s %= p; if(s < 0L) s += p; return s; } private static int minAll(int[] dt4min) { int min = INF; for(int i=0; i 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; //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; //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はarray public void ai(int[]... array) { for(int i=0; i