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 { //私が好きなアルゴリズム : 累積和・UF木 //PriorityQueueは拡張for文で出すとsortされてない順番で出てくるよ //longのbit演算は1L< cf) { d ++; cf = (1L<= cf) { d ++; cf *= 10L; } return d; //numはd桁の数で、10^dより小さい } private static int divceil(int nume, int deno) { return (nume+deno-1)/deno; } private static long divceil(long nume, long deno) { return (nume+deno-1L)/deno; } private static boolean isINF(long in) { if((in*20L)>INF) return true; else return false; } private static boolean isINFL(long in) { if((in*10L)>INFL) return true; else return false; } 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 biSearchMaxAL(ArrayList dt, long target) { int left=-1, right=dt.size(), mid=-1; while((right-left)>1) { mid = (right+left)/2; if(dt.get(mid) <= target) left=mid; else right=mid; } return left;//target以下の最大のaddress } 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}; private static boolean is_in_area(int y, int x, int h, int w) { if(y < 0) return false; if(x < 0) return false; if(y >= h) return false; if(x >= w) return false; return true; } 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) ? 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 minN(int... ins) { int min = ins[0]; for(int i=1; i max) max = ins[i]; } return max; } private static long maxN(long... ins) { long max = ins[0]; for(int i=1; i max) max = ins[i]; } return max; } private static int minExAd(int[] dt, int ad) { int min = Integer.MAX_VALUE; for(int i=0; imax)) max = dt[i]; } return max; } private static long maxExAd(long[] dt, int ad) { long max = Long.MIN_VALUE; for(int i=0; imax)) max = dt[i]; } return max; } private static int maxExVal(int[] dt, int ex_val) { int max = Integer.MIN_VALUE; for(int i=0; imax)) max = dt[i]; } return max; } private static long maxExVal(long[] dt, long ex_val) { long max = Long.MIN_VALUE; for(int i=0; imax)) max = dt[i]; } return max; } private static int sumA(int[] dt) { int sum = 0; for(int e: dt) { sum += e; } return sum; } private static long sumA(long[] dt) { long sum = 0L; for(long e: dt) { sum += e; } return sum; } private static long sumA(ArrayList dt) { long sum =0L; for(long e: dt) { sum += e; } return sum; } private static int pow(int n, int k) { int ans = 1; for(int i=0; i=0); } return ans; } private static long pow(long n, int k) { long ans = 1L; for(int i=0; i=0L); } return ans; } private static double hypod(double a, double b) { return Math.sqrt(a*a+b*b); } 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 a) { if(a==1) return false; for(long i=2L; i<=Math.sqrt(a); i++) { if(a%i == 0) return false; } return true; } private static long modinv(long a, long p) { assertion((a>0)&&(p>1)&&(a%p != 0)); //a|p, >1に注意 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; } u %= p; if(u < 0L) u += p; return u; } private static long pow10E97(long ob, long soeji, long p) { //繰り返し二乗法 if(ob==0) return 0L; if(soeji==0) return 1L; if(soeji==2) return (ob*ob)%p; long cf = 1L; int d = 0; while(soeji >= cf) { d ++; cf = (1L<=0L; i--) { if(soeji >= (1L< 0) return true; else return false; } private static boolean isFlaged(long bit, int pos) { if((bit&(1L< 0L) return true; else return false; } private static int ideflag(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<63; i++) { if((bit&(1L< 0) ans++; } return ans; } 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; } private static void show2(int bit) { for(int i=0; i dt) { //上手くいかなかった時用 long a=0; while(dt.size()>0) { a=dt.removeFirst(); System.out.print(a); } System.out.println("\n"); } static void show2(List dt) { //上手くいかなかった時用 for(int i=0; i Integer.MAX_VALUE) throw new NumberFormatException(); return (int) nl; } public double nexD() { return Double.parseDouble(next());} public void al(long[] array) { for(int i=0; i dt = new ArrayList<>(); Graph0n(int sz) { for(int i = 0; i < sz; i++) { Node0n node1 = new Node0n(); dt.add(node1); } } public void add(int vn, int val) { dt.get(vn).add(val); } public void add2(int vn, int val) { dt.get(vn).add(val); dt.get(val).add(vn); } public int get(int vn, int index) { return dt.get(vn).get(index); } public ArrayList get(int vn) { return dt.get(vn).getAll(); } public int size() { return dt.size(); } public int sizeOf(int vn) { return dt.get(vn).size(); } public void clear() { for(int i = 0; i < dt.size(); i++) { dt.get(i).clear(); } } public void clear(int i) { dt.get(i).clear(); } public static Graph0n make_tree(int vn, FastScanner sc) { Graph0n tree = new Graph0n(vn); for(int i = 1; i < vn; i++) { int s1 = sc.nexI() - 1; int g1 = sc.nexI() - 1; tree.add2(s1, g1); } return tree; } private void add_Vertex(Node0n vnew) { dt.add(vnew); } } static class Node0n { // 重みなし無向・有向グラフの頂点 private ArrayList next_vs = new ArrayList<>(); public void add(int val) { next_vs.add(val); } public int get(int ad) { return next_vs.get(ad); } public ArrayList getAll() { return next_vs; } public int size() { return next_vs.size(); } public void clear() { next_vs.clear(); } public void addAll(Node0n vnew) { this.next_vs.addAll(vnew.next_vs); } } static class Edge { int from=-1, v2=-1; long weight; public Edge(int vn, long w) { this.v2 = vn; this.weight = w; } public Edge(int cm, int vn, long w) { this.from = cm; this.v2 = vn; this.weight = w; } } static class Edge2 { int v2; long cost1,cost2; public Edge2(int vn, long w1, long w2) { this.v2 = vn; this.cost1 = w1; this.cost2 = w2; } } static class CompEdge_float implements Comparator{ //今は小さいのが前に出てくる public int compare(Edge a, Edge b) { if(a.weight>b.weight) return 1; else if(a.weight