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 primes = new HashSet<>(); for(long i=2L; i<5000010; i++){ primes.add(i); } for(long i=2; i<2500; i++){ if(primes.contains(i)){ for(long j=2L; j<=divceil(5000010,i); j++){ primes.remove(i*j); } } } for(int t=0; t=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 int sumA(int[] dt){ int sum =0; for(int e: dt){ sum += e; } return sum; } private static long sumA(long[] dt){ long sum =0; for(long e: dt){ sum += e; } return sum; } private static int sumA(List dt){ int sum =0; for(long e: dt){ sum += e; } return sum; } 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 boolean triangle_inequality(int a, int b, int c){ if((a+b)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(long i=2L; 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 = 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 < 0) u += p; return u; } private static int pow(int n, int k){ int ans=1; for(int i=0; i= cf){ d++; cf = (1L<= 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&(1L< 0) 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 0) ans++; } return ans; } private static void show2(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[] 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 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