import java.util.*; import java.io.*; import java.math.*; public class Main { static class Graph0n { private ArrayList dt = new ArrayList<>(); Graph0n(int sz){ for(int i=0; i get(int vn){ return dt.get(vn).getAll(); } public int sizeOf(int vn){ return dt.get(vn).size(); } public void clear(){ for(int i=0; i 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(); } } 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 Comparator_Edge implements Comparator{ public int compare(Edge a, Edge b){ if(a.weight>b.weight) return -1; else if(a.weight=0; i--){ rmin[i] = min(rmin[i+1], as[i]); } long ans = INFL; for(int i=1; i=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 minN(long... ins){ long min = ins[0]; for(int i=1; i max) max = ins[i]; } return max; } private static int minExAd(int[] dt, int ad){ int min=INF; for(int i=0; i max)) max = dt[i]; } return max; } private static long maxExAd(long[] dt, int ad){ long max=-INFL; for(int i=0; i max)) max = dt[i]; } return max; } private static int maxExVal(int[] dt, int ex_val){ int max=-INF; for(int i=0; i max)) max = dt[i]; } return max; } private static long maxExVal(long[] dt, long ex_val){ long max=-INFL; for(int i=0; i max)) max = dt[i]; } return max; } private static boolean same3(long a, long b, long c){ if(a!=b) return false; if(b!=c) return false; if(c!=a) return false; return true; } private static boolean dif3(long a, long b, long c){ if(a==b) return false; if(b==c) return false; if(c==a) return false; return true; } private static double hypod(double a, double b){ return Math.sqrt(a*a+b*b); } private static long factorial(int n) { long ans=1; for(long i=n; i>0; i--){ ans*=i; } return ans; } private static long facP(int n, long p) { long ans=1; for(long i=n; i>0; i--){ ans*=i; ans %= p; } return ans; } private static long lcm(long m, long n){ long ans = m/gcd(m,n); ans *= n; return ans; } private static long gcd(long m, long n) { 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(int i=2; i<=Math.sqrt(a); i++){ if(a%i == 0) return false; } return true; } private static long modinv(long a, long p) { //a|p, >1に注意 long b = p, u = 1, v = 0; 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 < 0) u += p; return u; } private static long[] fac10E97 = null; private static long[] finv10E97 = null; private static void Cinit(int max_sz, long p){ fac10E97 = new long[max_sz+1]; finv10E97 = new long[max_sz+1]; fac10E97[0]=1; finv10E97[0]=1; for(int i=1; i<=max_sz; i++){ fac10E97[i] = (fac10E97[i-1]*i) % p; } finv10E97[max_sz] = modinv(fac10E97[max_sz], p); for(int i=max_sz; i>1; i--){ finv10E97[i-1] = (finv10E97[i]*i) % p; } } private static long C10e97(int n, int k, long p){ long ans = fac10E97[n]; ans *= finv10E97[k]; ans %= p; ans *= finv10E97[n-k]; ans %=p; if(ans<0) return ans+p; else return ans; } private static long C10e97LS(long n, int k, long p){ long ans =1; for(long i=n; i>(n-(long)k); i--){ ans *= i; ans %= e97; } ans *= modinv(facP(k,e97),e97); return ans%e97; } private static int pow(int n, int k){ int ans=1; for(int i=0; i= cf){ d++; cf = 1<= cf){ d++; cf*=10; } return d; //numはd桁の数で、10^dより小さい } private static boolean isINF(int in){ if(((long)in*20)>INF) return true; else return false; } private static boolean isINFL(long in){ if((in*10000)>INFL) return true; else return false; } private static long pow10E97(long ob, long soeji, long p){ if(ob==0) return 0; if(soeji==0) return 1; if(soeji==2) return (ob*ob)%p; int d = getDigit2(soeji); long[] ob_pow_2pow = new long[d]; ob_pow_2pow[0] = ob; for(int i=1; i=0; i--){ if(soeji >= (long)(1< 0) return true; else return false; } private static boolean isFlaged(long bit, int pos){ if((bit&(1< 0) return true; else return false; } private static int deflag(int bit, int pos){ return bit&~(1< 0) ans++; } return ans; } private static void showflag(int bit){ for(int i=0; i1){ mid = left + (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(); int mid=-1; while((right-left)>1){ mid = left + (right-left)/2; if(dt.get(mid) <= target) left=mid; else right=mid; } return left;//target以下の最大のaddress } private static int get_root_uf(int[] parent, int index){ if(parent[index] == index) return index; int root = get_root_uf(parent, parent[index]); parent[index] = root; return root; } private static boolean is_same_uf(int[] parent, int x, int y){ if(get_root_uf(parent,x) == get_root_uf(parent,y)) return true; else return false; } private static void unite_uf(int[] parent, int receiver, int attacker){ parent[get_root_uf(parent,attacker)] = get_root_uf(parent, receiver); } 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; } static void show2(boolean[][] dt, int lit_x, int lit_y){ PrintWriter out = new PrintWriter(System.out); for(int j=0; j dt){ //上手くいかなかった時用 long a=0; while(dt.size()>0){ a=dt.removeFirst(); System.out.print(a); } System.out.println("\n"); } static void disp_list(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 ni(long[] array2){ for(int i=0; i