結果

問題 No.1616 Joke
ユーザー kps
提出日時 2021-07-22 21:31:31
言語 Java
(openjdk 23)
結果
AC  
実行時間 59 ms / 2,000 ms
コード長 52,129 bytes
コンパイル時間 4,339 ms
コンパイル使用メモリ 96,748 KB
実行使用メモリ 37,664 KB
最終ジャッジ日時 2024-07-17 16:36:56
合計ジャッジ時間 6,059 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/*
    created by krps
    本体は590行目あたりのsolve()に書いてあります。
    Good Luck!
 */
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.util.AbstractMap;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;
public class Main implements Runnable {
    public static void main(String[] args) {
        new Thread(null, new Main(), "", 1024 * 1024 * 1024).start(); //16MBスタックを確保して実行
    }
    public void run() {
        for(int i=0;i<1;i++) {
            solver();
            out.flush();
        }
    }
    static FastScanner sc = new FastScanner();
    static PrintWriter out = new PrintWriter(System.out);
        public static class Pair<K, V> extends AbstractMap.SimpleEntry<K, V> implements Comparable<Pair<K, V>> {
            public Pair(final K key, final V value) {
                super(key, value);
            }
            @Override
            public int compareTo(Pair<K, V> o) {
                Comparable key = (Comparable)this.getKey();
                Comparable key2 = (Comparable)o.getKey();
                /*if (false) {
                    Comparable key3 = (Comparable) this.getValue();
                    Comparable key4 = (Comparable) o.getValue();
                    if (key.compareTo(key2) == 0) {
                        return key3.compareTo(key4);
                    }
                }*/
                return key.compareTo(key2);
            }
        }
    private static boolean isPrime(long t) {
        if(t<2)return false;
        for(int i=2;i*i<=t;i++) {
            if(t%i==0)return false;
        }
        return true;
    }
    @SuppressWarnings("unused")
    private static long ncr(long n,long r) {
        long res=1;
        for(int i=0;i<r;i++) {
            res*=n-i;
            res/=i+1;
        }
        return res;
    }
    @SuppressWarnings("unused")
    private static int StringCount(String T,String v) {
        int res=0;
        int t=0;
        while(T.indexOf(v,t)>=0) {
            //p(t);
            res++;
            t=T.indexOf(v,t)+1;
        }
        return res;
    }
    private static int arrayMin(int a[]) {
        int res=INF;
        for(int i=0;i<a.length;i++)res=min(res,a[i]);
        return res;
    }
    private static long arrayMin(long a[]) {
        long res=INF;
        for(int i=0;i<a.length;i++)res=min(res,a[i]);
        return res;
    }
    private static int arrayMax(int a[]) {
        int res=-INF;
        for(int i=0;i<a.length;i++)res=max(res,a[i]);
        return res;
    }
    private static long arrayMax(long a[]) {
        long res=-INF;
        for(int i=0;i<a.length;i++)res=max(res,a[i]);
        return res;
    }
    private static long arraySum(long a[]) {
        long res=0;
        for(int i=0;i<a.length;i++)res+=a[i];
        return res;
    }
    private static int arraySum(int a[]) {
        int res=0;
        for(int i=0;i<a.length;i++)res+=a[i];
        return res;
    }
    private static void swap(long V[],int a,int b) {
        long temp=V[b];
        V[b]=V[a];
        V[a]=temp;
    }
    private static void p(long[][] a) {for(int i=0;i<a.length;i++)p(a[i]);};
    private static void p(long[] a) {p(Arrays.toString(a));};
    private static void p(int[][] a) {for(int i=0;i<a.length;i++)p(a[i]);};
    private static void p(int[] a) {p(Arrays.toString(a));};
    //大量にout.println();をすると、自動でout.flush();されるので、出力される順番には気を付けよう
    // * out.println()の後にSystem.out.println();をしたいときとかねー
    private static <T> void p(T t) {out.println(t);}
    private static <T> void p() {out.println();}
    private static void p(graph.edge2[] e) {
        for (int i = 0; i < e.length; i++) {
            out.println(e[i].to+" "+e[i].cost);
        }
    }
    private static void doubleToString(double a) {
        System.out.println(BigDecimal.valueOf(a).toPlainString());
    }
    private static ArrayList<Map<Integer,Integer>> c;
    private static <T> int[] ArrayListToList(ArrayList<Integer> c2,int[] v) {for(int i=0;i<c2.size();i++)v[i]=c2.get(i);return v;}
    private static ArrayList<Integer> ListToArrayList(int[] v) {ArrayList<Integer> c=new ArrayList<>(v.length);for(int i=0;i<v.length;i++)c.add(v[i]
        );return c;}
    private static String maenizero(String s,int keta) {
        while(s.length()<keta)s="0"+s;
        return s;
    }
    private static int ketawa(String S) {
        int res=0;
        for(int i=0;i<S.length();i++) {
            res+=S.charAt(i)-'0';
        }return res;
    }
    private static int ketawa(int S) {
        int res=0;
        while(S!=0) {
            res+=S%10;
            S/=10;
        }
        return res;
    }
    private static long X_x[]=new long[1];
    private static long kaijou(int x,long mod) {
        if(X_x.length!=100001)X_x=new long[100001];
        if(x<=1)return X_x[x]=1;
        if(X_x[x]!=0)return X_x[x];
        return X_x[x]=(x*kaijou(x-1,mod))%mod;
        /*long a=1;
        for(int i=2;i<=K;i++)a=(a*i)%mod;
        return (int)a;*/
    }
    static class segmentTree{
        int n;
        long dat[];
        long identity;//単位元
        segmentTree(int N,long identity) {//setTreeの要素の数,単位元
            this.identity =identity;
            init(N);
        }
        void init2() {
            Arrays.fill(dat, 0);
        }
        void init(int n_) {
            this.n=1;
            while(n<n_)n*=2;
            this.dat= new long[2*n-1];
            Arrays.fill(dat, identity);
        }
        void update(int k,long a) {
            k+=n-1;
            dat[k]=a;
            while(k>0) {
                k=(k-1)/2;
                //System.err.println("update "+k+" "+Cal(this.dat[k*2+1],this.dat[k*2+2]));
                dat[k]=Cal(dat[k*2+1],dat[k*2+2]);
            }
        }
        //外から呼び出すときはl=0,r=-1,k=0にする。
        void update(int a,int b,int k,int X,int l,int r) {
            if(r==-1)r=n;
            if(r<=a||b<=l) {
                return;
            }
            if(a<=l&&r<=b) {
                dat[k]=min(dat[k],X);
            }else {
                update(a, b, k*2+1,X, l, (l+r)/2);
                update(a, b,k*2+2,X,(l+r)/2,r);
            }
        }
        long get(int k) {//k番目の値を取得 0<=k<N
            k+=n-1;
            return dat[k];
        }
        //[a,b]を求める。
        //a~bのこと。0-indexed
        long getV(int a,int b) {
            a=max(0,a);
            b=min(n-1,b);
            b++;
            return query(a, b, 0, 0, n);
        }
        int getleft(int a,int b,long x) {
            return find_leftest_sub(a, b, x, 0, 0, n);
        }
        int getright(int a,int b,long x) {
            return find_rightest_sub(a, b, x, 0, 0, n);
        }
        //[a,b)の値を求める
        //a~b-1のことで、0-indexed
        //外から呼び出すときは、a,b,0,0,N
        long query(int a,int b,int k,int l,int r) {
            if(r<=a||b<=l) {
                //l,rが求めたい区間a,bに完全に含まれていない
                return identity;
            }
            if(a<=l&&r<=b) {
                //l,rが、求めたい区間a,bに完全に含まれている
                return dat[k];
            }else {
                //l,rが、求めたい区間a,bに一部分だけ含まれている。
                long A=query(a, b, k*2+1, l, (l+r)/2);
                long B=query(a, b, k*2+2, (l+r)/2, r);
                return Cal(A,B);
            }
        }
        //x以下の要素を持つ最も左のもののindexを返す。 *RM(min)Q上でしか動かない
         int find_rightest_sub(int a, int b, long x, int k, int l, int r) {
                if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1
                    return a - 1;
                } else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
                    return (k - (n - 1));
                } else {
                    int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
                    if (vr != a - 1) {  // 右の部分木を見て a-1 以外ならreturn
                        return vr;
                    } else {  // 左の部分木を見て値をreturn
                        return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
                    }
                }
            }
            int find_leftest_sub(int a, int b, long x, int k, int l, int r) {
                if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b
                    return b;
                } else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
                    return (k - (n - 1));
                } else {
                    int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
                    if (vl != b) {  // 左の部分木を見て b 以外ならreturn
                        return vl;
                    } else {  // 右の部分木を見て値をreturn
                        return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
                    }
                }
            }
            //RSQ上で動きます。
        int query2(long X) {
            int k=0;
            //ここでは、Σ[0,r]Ai=Xとなる最小のrを求めたい
            while(k*2+1<dat.length) {
                if(dat[k*2+1]>=X) {
                    k=k*2+1;
                }else {
                    X-=dat[k*2+1];
                    k=k*2+2;
                }
            }
            return k-=n-1;
        }
        long Cal(long a,long b) {
            //計算アルゴリズム
            return (a+b);
            //return a|b;
            //return max(a,b);
            //return gcd(a, b);
            //return a^b;
            //return Math.min(a, b);
        }
        int size() {
            //Nではないよ、配列の大きさを返す。
            return n;
        }
        //確認事項:Calとidentity
        //segmentTreeで宣言、initで初期化する。
        void toString(int n) {
            for(int i=0;i<n*2;i++) {
                System.err.print(dat[i]+" ");
            }
            System.err.println();
        }
    }
    static class LazySegmentTree{
        int n;
        long node[],lazy[];
        int identity;
        long cal(long a,long b) {
            return a+b;
        }
        public LazySegmentTree(long[] A,int iden) {
            // TODO 自動生成されたコンストラクター・スタブ
            init(A);
            identity=iden;
        }
        //初期化
        void init(long A[]) {
            n=1;
            int sz=A.length;
            while(n<sz)n*=2;
            node=new long[2*n-1];
            lazy=new long[2*n-1];
            for(int i=0;i<sz;i++)node[i+n-1]=A[i];
            for(int i=n-2;i>=0;i--)node[i]=cal(node[i*2+1],node[i*2+2]);
        }
        void eval(int k,int l,int r) {
            //k番目のノードについて、遅延評価を行う？
            // 遅延配列が空でない場合、自ノード及び子ノードへの
            // 値の伝播が起こる
            if(lazy[k]!=identity) {
                node[k]+=lazy[k];
                System.out.println(r);
                if(r-1>1) {//最下段かどうか
                    lazy[2*k+1]=cal(lazy[k]/2, lazy[2*k+1]);//ここもRSQ以外未定義 /2するところを要変更
                    lazy[2*k+2]=cal(lazy[k]/2, lazy[2*k+1]);
                     // 子ノードは親ノードの 1/2 の範囲であるため、
                    // 伝播させるときは半分にする
                }
                lazy[k]=identity;
            }
        }
        //区間加算,外から呼び出すときは、l=0,r=-1
        void add(int a,int b,long x,int k,int l,int r) {
            //[a,b)の区間にxを加算する。
            if(r<0)r=n;
            eval(k,l,r);
            if(b<=l||r<=a)return;
            if(a<=l&&r<=b) {
                lazy[k]=cal((r-1)*x,lazy[k]);//ここもRSQ以外未定義 *xするところを要変更
                eval(k, l, r);
            }else {
                add(a, b, x, 2*k+1, l, (l+r)/2);
                add(a, b, x, 2*k+2, (l+r)/2, r);
                node[k]=cal(node[2*k+1],node[2*k+2]);
            }
        }
        //区間和取得,外から呼び出すときは、l=0,r=-1
        long getsum(int a,int b,int k,int l,int r) {
            if(r<0)r=n;
            if(b<=l||r<=a)return 0;
            eval(k, l, r);
            if(a<=l&&r<=b)return node[k];
            long vl=getsum(a, b, 2*k+1, l, (l+r)/2);
            long vr=getsum(a, b, 2*k+2, (l+r)/2, r);
            return cal(vl,vr);
            }
    }
    static class IntsegmentTree{
        int n;
        int dat[];
        int identity;//単位元
        IntsegmentTree(int N,int identity) {//setTreeの要素の数,単位元
            this.identity =identity;
            init(N);
        }
        void init2() {
            Arrays.fill(dat, 0);
        }
        void init(int n_) {
            this.n=1;
            while(n<n_)n*=2;
            this.dat= new int[2*n-1];
            Arrays.fill(dat, identity);
        }
        void update(int k,int a) {
            k+=n-1;
            dat[k]=a;
            while(k>0) {
                k=(k-1)/2;
                //System.err.println("update "+k+" "+Cal(this.dat[k*2+1],this.dat[k*2+2]));
                dat[k]=Cal(dat[k*2+1],dat[k*2+2]);
            }
        }
        //外から呼び出すときはl=0,r=-1,k=0にする。
        void update(int a,int b,int k,int X,int l,int r) {
            if(r==-1)r=n;
            if(r<=a||b<=l) {
                return;
            }
            if(a<=l&&r<=b) {
                dat[k]=min(dat[k],X);
            }else {
                update(a, b, k*2+1,X, l, (l+r)/2);
                update(a, b,k*2+2,X,(l+r)/2,r);
            }
        }
        int get(int k) {//k番目の値を取得 0<=k<N
            k+=n-1;
            return dat[k];
        }
        //[a,b]を求める。
        //a~bのこと。0-indexed
        int getV(int a,int b) {
            a=max(0,a);
            b=min(n-1,b);
            b++;
            return query(a, b, 0, 0, n);
        }
        int getleft(int a,int b,long x) {
            return find_leftest_sub(a, b, x, 0, 0, n);
        }
        int getright(int a,int b,long x) {
            return find_rightest_sub(a, b, x, 0, 0, n);
        }
        //[a,b)の値を求める
        //a~b-1のことで、0-indexed
        //外から呼び出すときは、a,b,0,0,N
        int query(int a,int b,int k,int l,int r) {
            if(r<=a||b<=l) {
                //l,rが求めたい区間a,bに完全に含まれていない
                return identity;
            }
            if(a<=l&&r<=b) {
                //l,rが、求めたい区間a,bに完全に含まれている
                return dat[k];
            }else {
                //l,rが、求めたい区間a,bに一部分だけ含まれている。
                int A=query(a, b, k*2+1, l, (l+r)/2);
                int B=query(a, b, k*2+2, (l+r)/2, r);
                return Cal(A,B);
            }
        }
        //x以下の要素を持つ最も左のもののindexを返す。 *RM(min)Q上でしか動かない
         int find_rightest_sub(int a, int b, long x, int k, int l, int r) {
                if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1
                    return a - 1;
                } else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
                    return (k - (n - 1));
                } else {
                    int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
                    if (vr != a - 1) {  // 右の部分木を見て a-1 以外ならreturn
                        return vr;
                    } else {  // 左の部分木を見て値をreturn
                        return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
                    }
                }
            }
            int find_leftest_sub(int a, int b, long x, int k, int l, int r) {
                if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b
                    return b;
                } else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
                    return (k - (n - 1));
                } else {
                    int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
                    if (vl != b) {  // 左の部分木を見て b 以外ならreturn
                        return vl;
                    } else {  // 右の部分木を見て値をreturn
                        return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
                    }
                }
            }
            //RSQ上で動きます。
        int query2(int X) {
            int k=0;
            //ここでは、Σ[0,r]Ai=Xとなる最小のrを求めたい
            while(k*2+1<dat.length) {
                if(dat[k*2+1]>=X) {
                    k=k*2+1;
                }else {
                    X-=dat[k*2+1];
                    k=k*2+2;
                }
            }
            return k-=n-1;
        }
        int Cal(int a,int b) {
            //計算アルゴリズム
            return (a+b);
            //return a|b;
            //return max(a,b);
            //return gcd(a, b);
            //return a^b;
            //return Math.min(a, b);
        }
        int size() {
            //Nではないよ、配列の大きさを返す。
            return n;
        }
        //確認事項:Calとidentity
        //segmentTreeで宣言、initで初期化する。
        void toString(int n) {
            for(int i=0;i<n*2;i++) {
                System.err.print(dat[i]+" ");
            }
            System.err.println();
        }
    }
    static void B(boolean x) {
        p(x? "Yes":"No");
    }
    static void B(boolean x, String a,String b) {
        p(x? a:b);
    }
    static int[][] clone(int V[][]) {
        int RES[][]=new int[V.length][V[0].length];
        for (int i = 0; i < V.length; i++) {
            for (int t = 0; t < V[0].length; t++) {
                RES[i][t]=V[i][t];
            }
        }
        return RES;
    }
    static class D {
        int a,b;
    }
    static void comp(int a[]) {
        binarySerch bs = new binarySerch();
        int b[]=a.clone();
        Arrays.parallelSort(b);
        for (int i = 0; i < a.length; i++) {
            a[i]=bs.lowerBound(b, a[i])+1;
            compmax=max(compmax,a[i]);
        }
    }
    static long ceil(long a,long b) {
        //ceil(a/b)を返す。
        //a/bの切り上げ
        return (a+b-1)/b;
    }
    static long floor(long a,long b) {
        //floor (a/b)を返す。
        //a/bの切り捨て
        return a/b;
    }
    //Math.multiplyExact(T, A[i])
    static class V implements Comparable<V>{
        int y,z;
        int x,a,b,C;
        int count;
        int dep;
        String S;
        V(int x,int y){
            this.x=x;
            this.y=y;
        }
        V(int a,int b,int C){
            this.a=a;
            this.b=b;
            this.x=C;
        }
        public int compareTo(V o) {
            Comparable key = (Comparable)this.x;
            Comparable key2 = (Comparable)o.x;
            Comparable key3 = (Comparable)this.y;
            Comparable key4 = (Comparable)o.y;
            if(key.compareTo(key2)==0) {
                return key3.compareTo(key4);
            }
            return key.compareTo(key2);
 
        }
    }
    static long LINF =(1L<<63)-1,mod7=Pow(10,9)+7,mod9=Pow(10,9)+9,count=0,sum=0,max=-LINF,min=LINF,ans=0,temp;
    static int i=0,INF=(1<<31)-1,compmax=0;
    static long A[];
    private static void solver() {
        int N = sc.nextInt();
        System.out.println(N);
        
    }
    /*long kruskal(int V,edge es[]) {
        unionFind uf = new unionFind(V);
        Arrays.sort(es);
        long res=0;
        for (int i = 0; i < es.length; i++) {
            if(uf.find( es[i].from)!=uf.find( es[i].to)) {
                uf.union(es[i].from, es[i].to);
                res+=es[i].cost;
            }
        }
        return res;
    }*/
    //関数Fについて、区間[a,b]の最小値を求める
        static void tripet(long a,long b) {
            long max=max(a,b),min=min(a,b);
            while(max-min>2){
                long c1=(max-min)/3+min;
                long c2=(max-min)*2/3+min;
                if(F(c1)>=F(c2)) {
                    min=c1;
                }else{
                    max=c2;
                }
            }
            for(long i=min-1;i<=max+1;i++) {
                F(i);
            }
        }
        static long F(long V) {
            long res=0;
            //b0をVに固定する
            long b=V;
            long c=A[0]-b;
            res+=abs(b)+abs(c);
            for (int i = 1; i < A.length; i++) {
                if(A[i]>A[i-1]) {
                    //増加した。
                    b=A[i]-c;
                }else if(A[i]<A[i-1]) {
                    //減少した
                    c=A[i]-b;
                }
                res+=abs(b)+abs(c);
                if(res<0)res=LINF;
            }
            min=min(min,res);
            return res;
        }
    static long getF(long a,long b,long c,long d) {
        //[a,b]と[c,d]の区間数の和
        
        
        if(b<c||a>d) {
            //完全に含まれない。
            return (b-a+1)+(d-c+1);
        }
        if(c<=a&&b<=d) {
            //完全に含まれる1
            return d-c+1;
        }
        if(a<=c&&d<=b) {
            //完全に含まれる2
            return b-a+1;
        }
        
        //一部だけ含まれる。
        if(c<=b&&b<=d) {
            //[c,b]が含まれる。
            return d-a+1;
        }
        if(c<=a&&a<=d) {
            return b-c+1;
        }
        return -1;
        
    }
    
    
    
    static boolean check(int HW[][],int i,int t,int W) {
        while(t<W) {
            if(HW[i][t]%2==1)return true;
            t++;
        }
        return false;
    }   
    
    static void SCC(Map<Integer,ArrayList<Integer>> m,int N) {
        int BACK[]=new int[N];
        Arrays.fill(BACK, -1);
        
        for (int i = 0; i < N; i++) {
            if(BACK[i]!=-1)continue;
            getBackQuery(m, i, BACK);
            BACK[BACK_COUNT]=i;
        }
        Map<Integer,ArrayList<Integer>> reversedm=new HashMap<>();
        for(int Vex:m.keySet()) {
            for(int TO:m.get(Vex)) {
                if(!reversedm.containsKey(TO))reversedm.put(TO, new ArrayList<>());
                reversedm.get(TO).add(Vex);
            }
        }
        uf=new unionFind(N);
        for (int i = N-1; i>=0;i--) {
            //iを始点として、DFSを行う。到達可能マスが同じグループ
            if(uf.get(i)!=i)continue;
            sccquery(reversedm, i);
        }
    }
    static void sccquery(Map<Integer,ArrayList<Integer>> reversedm,int vex) {
        if(!reversedm.containsKey(vex)||reversedm.get(vex).size()==0)return;
        for(int TO:reversedm.get(vex)) {
            if(uf.find(vex)==uf.find(TO))continue;
            uf.union(vex, TO);
            sccquery(reversedm, vex);
        }
    }
    static int BACK_COUNT;
    static unionFind uf;
    static void getBackQuery(Map<Integer,ArrayList<Integer>> m,int Vex,int BACK[]) {
        if(!m.containsKey(Vex)||m.get(Vex).size()==0)return;
        for(int TO:m.get(Vex)) {
            if(BACK[TO]!=-1)continue;
            BACK[TO]=-2;
            getBackQuery(m, Vex, BACK);
            BACK[BACK_COUNT++]=TO;
        }
    }
    
    
    static ArrayList<Integer> Vs;
    static void getTopo(Map<Integer,ArrayList<Integer>> m,int N) {
        boolean flag[]=new boolean[N];
        Arrays.fill(flag, false);
        Vs=new ArrayList<>();
        for(int V:m.keySet()) {
            if(flag[V])continue;
            flag[V]=true;
            topoQuery(m, V, flag);
            Vs.add(V);
        }
        Collections.reverse(Vs);
    }
    static void topoQuery(Map<Integer,ArrayList<Integer>> m,int Vex, boolean flag[]) {
        //Vexからスタート
        //これ、閉路がある時に対応できてなくね
        if(!m.containsKey(Vex)||m.get(Vex).size()==0)return;
        for(int to:m.get(Vex)) {
            if(flag[to])continue;
            flag[to]=true;
            topoQuery(m, to,flag);
            Vs.add(to);
            
            
        }
        
    }
    static class Flow{
        static class edge{
            int to,cap,rev;
            public edge(int to,int cap,int rev) {
                // TODO 自動生成されたコンストラクター・スタブ
                this.to=to;
                this.cap=cap;
                this.rev=rev;
            }
        }
        
        public Flow(int N) {
            // TODO 自動生成されたコンストラクター・スタブ
            this.N=N;//頂点数
            init();
        }
        void init() {
            used=new boolean[N];
            G=new ArrayList<>();
            for (int i = 0; i < N; i++) {
                G.add(new ArrayList<>());
            }
        }
        int N;
        ArrayList<ArrayList<edge>> G;//iがfromを意味する 隣接リスト表現
        boolean used[];
        //from->toへ向かう容量capの辺をグラフに追加する。
        void add_edge(int from,int to,int cap) {
            G.get(from).add(new edge(to, cap, G.get(to).size()));
            G.get(to).add(new edge(from, 0, G.get(from).size()-1));
        }
        //最大流を求める 最悪計算量はO(F|E|) Fは流量,Eは辺の数?
        int max_flow(int s,int t) {
            int flow=0;
            while(true) {
                Arrays.fill(used, false);
                int f=dfs(s,t,INF);
                if(f==0)return flow;
                flow+=f;
            }
        }
        int dfs(int v,int t,int f) {
            if(v==t)return f;//tに到着したら終了
            used[v]=true;//vに訪れたことを表す
            for (int i = 0; i < G.get(v).size(); i++) {
                edge e=G.get(v).get(i);
                if(used[e.to]||e.cap<=0)continue;
                int d=dfs(e.to, t, Math.min(f,e.cap));
                if(d>0) {
                    e.cap-=d;
                    G.get(e.to).get(e.rev).cap+=d;
                    return d;
                }
            }
            return 0;
        }
        //デバッグ用
        void get_edges(int T) {
            //頂点Tから出る辺を出力する
            int cout=0;
            for(edge e:G.get(T)) {
                System.out.println(cout+++" "+T+"=>"+e.to+" "+e.cap);
            }
        }
    }
    static class LCA{
        int N;//頂点の数(頂点名は、0-indexで命名)
        int dist[];//rootから頂点iまでの距離
        int root;//木の根
        int parents[];//頂点iの親がparents[i]
        int doubling[][];
        public LCA(Map<Integer,ArrayList<Integer>> m,int N,int root) {  
            //一般グラフを受け取って、そこから木を生成する。
            this.root=root;
            init(m,N);
        }
        void init(Map<Integer,ArrayList<Integer>> m,int N) {
            this.N=N;
            parents=new int[N];
            dist=new int[N];
            doubling=new int[31][N];
            dfs(m);
            init_doubling();
        }
        void dfs(Map<Integer,ArrayList<Integer>> m) {
            //根からの距離と親を求める。
            boolean flag[]=new boolean[N];
            Arrays.fill(flag, false);
            flag[root]=true;
            parents[root]=root;
            Queue<Integer> qq = new ArrayDeque<>(); //始点を保存
            qq.add(root);
            while(!qq.isEmpty()) {
                int VEX=qq.poll();
                if(!m.containsKey(VEX)||m.get(VEX).size()==0)continue;
                for(int TO:m.get(VEX)) {
                    if(flag[TO])continue;
                    flag[TO]=true;
                    parents[TO]=VEX;
                    dist[TO]=dist[VEX]+1;
                    qq.add(TO);
                }
            }
        }
        void init_doubling() {
            //ダブリングによって、2^k先の祖先を前計算する。
            //doubling[T][i]=iから2^T個分先
            for (int i = 0; i < N; i++) {
                doubling[0][i]=parents[i];
            }
            for (int T = 1; T < doubling.length; T++) {
                for (int i = 0; i < N; i++) {
                    doubling[T][i]=doubling[T-1][doubling[T-1][i]];
                }
            }
        }
        int get_doubling(int from,int K) {
            //ダブリングによって、fromからK先の祖先を求める。
            //longにするときは、doublingの長さも変えないとだから注意
            int res=from;
            for (int i = 0; i < doubling.length; i++) {
                if(((K>>i)&1)==0)continue;
                res=doubling[i][res];
            }
            return res;
            
        }
        int query(int u1,int v1) {
            //親からの距離を等しくする。(dist[u1]>dist[v1]とする)
            //System.out.println(u1+" "+v1+" "+get_doubling(u1, dist[u1]-dist[v1]));
            u1=get_doubling(u1, dist[u1]-dist[v1]);
            if(u1==v1)return v1;
            //二分探索によって、LCAの手前まで移動させる。
            
            int G=30;
            while(G>=0) {
                int uTO=doubling[G][u1];
                int vTO=doubling[G][v1];
                if(uTO!=vTO) {
                    u1=uTO;
                    v1=vTO;
                }
                G--;
            }
            //System.out.println(parents[u1]+" "+parents[v1]+" "+dist[u1]+" "+dist[v1]+" "+u1+" "+v1);
            return parents[u1];
        }
        int get_LCA(int u,int v) {
            //根をrootとした時の、u,vのLCAを返す。(0-indexed)
            if(dist[u]<dist[v]) {
                int temp=u;u=v;v=temp;
            }
            //dist[u]>dist[v]とする。
            return query(u,v);
        }
        int get_dist(int u,int v) {
            //u-vの距離
            return dist[u]+dist[v]-2*dist[get_LCA(u, v)];
        }
        boolean is_on_path(int u,int v,int a) {
            //u-vパス上に頂点aがあるか?
            //true:ある
            //false:ない
            return get_dist(u, a)+get_dist(a, v)==get_dist(u, v);
        }
    }
    static class doubling{
        int N;
        int bits;
        int doubling[][];
        long COST[][];
        public doubling(int A[],int bits) {
            this.bits=bits;
            this.N=A.length;
            init1(A);
        }
        public doubling(int A[],int bits,long C[]) {
            // TODO 自動生成されたコンストラクター・スタブ
            //long C[]は、i=>A[i]に行くコスト
            //query2は、iからK番先までのコストの和で、i番までのコストが足されないので注意
            this.bits=bits;
            this.N=A.length;
            init1(A);
            init2(C);
        }
        private void init1(int A[]) {
            // TODO 自動生成されたメソッド・スタブ
            doubling=new int[bits][N];
            for (int i = 0; i < N; i++) {
                doubling[0][i]=A[i];
            }
            for (int t = 0; t+1 < bits; t++) {
                for (int i = 0; i < N; i++) {
                    doubling[t+1][i]=doubling[t][doubling[t][i]];
                }
            }
        }
        private void init2(long C[]) {
            COST=new long[bits][N];
            for (int i = 0; i < N; i++) {
                COST[0][i]=C[i];//i番目からA[i]までのコスト
            }
            for (int t = 0; t+1 < bits; t++) {
                for (int i = 0; i < N; i++) {
                    COST[t+1][i]=COST[t][doubling[t][i]]+COST[t][i];
                }
            }
        }
        //解釈
        private int query1(int start,long K) {
            //startからK回移動した後の座標を求める。
            int now=start;
            for (int i = 0; i < bits; i++) {
                if(((K>>i)&1)==1)now=doubling[i][now];
            }
            return now;
        }
        private long query2(int start,long K,long mod) {
            //STARTからK回移動した時のコストを計算する。
            int now=start;
            long res=0;
            for (int i = 0; i < bits; i++) {
                if(((K>>i)&1)==1) {
                    res+=COST[i][now];
                    now=doubling[i][now];
                    res%=mod;
                }
            }
            return res;
        }
        private int query3(int start) {
            //startからスタートして、ループに入る時、そのループの長さを返す。
            
            
            
            return 1;
        }
    }
    static class DIKSTR{
        ArrayList<ArrayList<edge2>> m;
        static Map<String,Integer> hash=new HashMap<>();
        static int hash_count=0;
        long d[];
        int V,E;
        class edge2{
            int to;
            long cost;
            public edge2(int to,long cost) {
                this.to=to;
                this.cost=cost;
            }
        }
        class pair implements Comparable<pair>{
            int VEX;
            long cost;
            public pair(long cost,int VEX) {
                this.VEX=VEX;
                this.cost=cost;
            }
            public int compareTo(pair o) {
                Comparable key = (Comparable)this.cost;
                Comparable key2 = (Comparable)o.cost;
                return key.compareTo(key2);
            }
        }
        public DIKSTR(int V,int E) {
            this.V=V;//最大の頂点数。
            this.E=E;//最大の辺数。
            init();
        }
        public DIKSTR(int V) {
            this.V=V;
            this.E=0;
            init();
        }
        void init() {
            m=new ArrayList<>();
            for (int i = 0; i < V; i++) {
                m.add(new ArrayList<>());
            }
            d=new long[V];
        }
        void add_edge(int FROM,int TO,long COST) {
            m.get(FROM).add(new edge2(TO, COST));
        }
        void add_edge(String FROM,String TO,long COST) {
            if(!hash.containsKey(FROM))hash.put(FROM, hash_count++);
            if(!hash.containsKey(TO))hash.put(TO, hash_count++);
            add_edge(get_hash(FROM), get_hash(TO), COST);
        }
        int get_hash(String T) {
            if(!hash.containsKey(T)) {
                hash.put(T, hash_count++);
            }
            return hash.get(T);
        }
        long[] dikstr(String r) {
            return dikstr(get_hash(r));
        }
        long[] dikstr(int r) {//rは始点
            Arrays.fill(d, LINF);
            d[r]=0;
            PriorityQueue<pair> p = new PriorityQueue<>();//add poll
            p.add(new pair(0L, r));
            while(!p.isEmpty()) {
                pair x=p.poll();
                int from=x.VEX;
                if(x.cost>d[from])continue;
                for (int i = 0; i < m.get(from).size(); i++) {
                    edge2 e=m.get(from).get(i);
                    long COST=COST(e.cost);
                    if(d[e.to]>d[from]+COST) {
                        d[e.to]=d[from]+COST;
                        p.add(new pair(d[e.to], e.to));
                    }
                }
            }
            return d.clone();
        }
        long COST(long e_cost) {
            
            
            return e_cost;
        }
    }
    
    
    static Map<Integer, ArrayList<Integer>> getTree(int N){
        Map<Integer, ArrayList<Integer>> m = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int a = sc.nextInt() - 1, b = sc.nextInt() - 1;
            if (!m.containsKey(a))
                m.put(a, new ArrayList<Integer>());
            if (!m.containsKey(b))
                m.put(b, new ArrayList<Integer>());
            m.get(a).add(b);
            m.get(b).add(a);
        }
        return m;
    }
    static Map<Integer, ArrayList<Integer>> makeTree(Map<Integer, ArrayList<Integer>> m){
        //頂点0を根とした木を構築する。
        Queue<Integer> qq = new ArrayDeque<>(); //add,poll,peek BFSは前から実行される
        Queue<Integer> parent = new ArrayDeque<>(); //add,poll,peek BFSは前から実行される
        qq.add(0);
        Map<Integer, ArrayList<Integer>> T = new HashMap<>();
        parent.add(-1);
        while (!qq.isEmpty()) {
            int i = qq.poll();
            int p = parent.poll();
            if (!T.containsKey(i))
                T.put(i, new ArrayList<Integer>());
            for (int V : m.get(i)) {
                if (V == p)
                    continue;
                qq.add(V);
                parent.add(i);
                T.get(i).add(V);
            }
        }
        return T;
    }
    static boolean isHaveSameBit(int a,int b) {//同じbitを持っているか
        int t=0;
        while((a>>t)!=0) {
            if(((a>>t)&1)==1&&((b>>t)&1)==1)return true;
            t++;
        }
        return false;
    }
    static boolean isPalindrome(String S) {//回分になってるか
        for (int i = 0; i < S.length()/2; i++) {
            if(S.charAt(i)!=S.charAt(S.length()-i-1)) {
                return false;
            }
        }
        return true;
    }
    static long modinv(long a,long mod) {
        long b=mod,u=1,v=0;
        while(b!=0) {
            long t=a/b;
            a-=t*b;long tem=a;a=b;b=tem;
            u-=t*v;tem=u;u=v;v=tem;
        }
        u%=mod;
        if(u<0)u+=mod;
        return u;
    }
    static long[] extendedGCD(long a, long b) {
        long s = 0, old_s = 1;
        long t = 1, old_t = 0;
        long r = b, old_r = a;
        while(r != 0) {
            long q = old_r / r;
            long old_s0 = old_s, old_t0 = old_t, old_r0 = old_r;
            old_s = s;
            s = old_s0 - q * s;
            old_t = t;
            t = old_t0 - q * t;
            old_r = r;
            r = old_r0 - q * r;
        }
        return new long[] {old_s, old_t};
    }
    static class graph{
        public graph() {
            // TODO 自動生成されたコンストラクター・スタブ
        }
        //コンテスト中だけ
        static class edge3{
            int to;
            long cost;
            int K;
            public edge3(int to,long cost) {
                this.to=to;
                this.cost=cost;
            }
            public edge3(int to,long cost,int K) {
                this.to=to;
                this.cost=cost;
                this.K=K;
            }
        }
        long costV(long T,int K) {
            //T以上の最小のKの倍数を返す。
            long V=(T+K-1)/K;
            return V*K;
        }
        long[] adddikstr(int V,int E,int r,Map<Integer, ArrayList<edge3>> m) {
            d=new long[V];
            Arrays.fill(d, LINF);
            d[r]=0;
            PriorityQueue<Pair<Long,Integer>> p = new PriorityQueue<>();//add poll
            p.add(new Pair<Long, Integer>(0L, r));
            while(!p.isEmpty()) {
                Pair<Long,Integer> x=p.poll();
                int from=x.getValue();
                if(x.getKey()>d[from])continue;
                if(!m.containsKey(from))continue;
                for (int i = 0; i < m.get(from).size(); i++) {
                    edge3 e=m.get(from).get(i);
                    if(d[e.to]>costV(d[from],e.K)+e.cost) {
                        d[e.to]=costV(d[from],e.K)+e.cost;
                        p.add(new Pair<Long, Integer>(d[e.to], e.to));
                    }
                }
            }
            return d;
        }
        //
        
        class edge implements Comparable<edge>{
            int from,to,cost;
            public edge(int from,int to,int cost) {
                this.from=from;
                this.to=to;
                this.cost=cost;
            }
            @Override
            public int compareTo(edge o) {
                Comparable key = (Comparable)this.cost;
                Comparable key2 = (Comparable)o.cost;
                return key.compareTo(key2);
            }
        }
        static class edge2{
            int to;
            long cost;
            String FROM,TO;
            public edge2(int to,long cost) {
                this.to=to;
                this.cost=cost;
            }
            public edge2(int to,long cost,String FROM,String TO) {
                this.to=to;
                this.cost=cost;
                this.FROM=FROM;
                this.TO=TO;
            }
        }
        //単一始点最短距離問題(ダイクストラ法) 負閉路対策不可 経路復元
        long d[];
        long[] dikstr(int V,int E,int r,Map<Integer, ArrayList<edge2>> m) {
            //int path[]=new int[V];
            //Arrays.fill(path, -1);
            d=new long[V];
            Arrays.fill(d, LINF);
            d[r]=0;
            PriorityQueue<Pair<Long,Integer>> p = new PriorityQueue<>();//add poll
            p.add(new Pair<Long, Integer>(0L, r));
            while(!p.isEmpty()) {
                Pair<Long,Integer> x=p.poll();
                int from=x.getValue();
                if(x.getKey()>d[from])continue;
                if(!m.containsKey(from))continue;
                for (int i = 0; i < m.get(from).size(); i++) {
                    edge2 e=m.get(from).get(i);
                    if(d[e.to]>d[from]+e.cost) {
                        d[e.to]=d[from]+e.cost;
                        p.add(new Pair<Long, Integer>(d[e.to], e.to));
                        //path[e.to]=from;
                    }
                }
            }
            //経路復元
            //複数の経路を考える必要がある時は、pathに複数の同じような最短経路の辺を保存しておく
            //ArrayList<Integer> PATHs = new ArrayList<>();
            //int t=V-1;//goalから逆算する この場合0=goal
            //for(;t!=-1;t=path[t]) {
            //  PATHs.add(t);
            //}
            //p(path);
            //Collections.reverse(PATHs);
            //System.out.println(PATHs);
            return d.clone();
        }
        long[] additionalDikstr(int V,int E,int r,Map<Integer, ArrayList<edge2>> m,int banned) {
            //int path[]=new int[V];
            //Arrays.fill(path, -1);
            d=new long[V];
            Arrays.fill(d, LINF);
            d[r]=0;
            PriorityQueue<Pair<Long,Integer>> p = new PriorityQueue<>();//add poll
            p.add(new Pair<Long, Integer>(0L, r));
            while(!p.isEmpty()) {
                Pair<Long,Integer> x=p.poll();
                int from=x.getValue();
                if(x.getKey()>d[from])continue;
                if(!m.containsKey(from))continue;
                for (int i = 0; i < m.get(from).size(); i++) {
                    edge2 e=m.get(from).get(i);
                    if(from==banned&&e.to==0)continue;
                    if(d[e.to]>d[from]+e.cost) {
                        d[e.to]=d[from]+e.cost;
                        p.add(new Pair<Long, Integer>(d[e.to], e.to));
                    }
                }
            }
            return d.clone();
        }
        int D[];
        int[] Intdikstr(int V,int E,int r,Map<Integer, ArrayList<edge2>> m) {
            //int path[]=new int[V];
            //Arrays.fill(path, -1);
            D=new int[V];
            Arrays.fill(D, INF);
            D[r]=0;
            PriorityQueue<Pair<Integer,Integer>> p = new PriorityQueue<>();//add poll
            p.add(new Pair<Integer, Integer>(0, r));
            while(!p.isEmpty()) {
                Pair<Integer,Integer> x=p.poll();
                int from=x.getValue();
                if(x.getKey()>D[from])continue;
                if(!m.containsKey(from))continue;
                for (int i = 0; i < m.get(from).size(); i++) {
                    edge2 e=m.get(from).get(i);
                    if(D[e.to]>D[from]+e.cost) {
                        D[e.to]=(int) (D[from]+e.cost);
                        p.add(new Pair<Integer, Integer>(D[e.to], e.to));
                        //path[e.to]=from;
                    }
                }
            }
            p.clear();
            //経路復元
            //複数の経路を考える必要がある時は、pathに複数の同じような最短経路の辺を保存しておく
            //ArrayList<Integer> PATHs = new ArrayList<>();
            //int t=V-1;//goalから逆算する この場合0=goal
            //for(;t!=-1;t=path[t]) {
            //  PATHs.add(t);
            //}
            //p(path);
            //Collections.reverse(PATHs);
            //System.out.println(PATHs);
            return D;
        }
        //単一始点最短距離問題(ベルマンフォード法) 負閉路対策済み
        int[] Bellman_Ford(int V,int E,int r,edge e[]) {
            int d[]=new int[V]; //0~eのグラフはこれ
            //Map<Integer, Integer> d = new HashMap<>();それ以外はこれ
            //for(int i=0;i<E;i++) {
            //  if(!d.containsKey(e[i].to))m.add(new Pair<Integer, Integer>(e[i].to, INF));
            //  if(!d.containsKey(e[i].from))m.add(new Pair<Integer, Integer>(e[i].from, INF));
            //}
            //d.replace(r, 0);
            Arrays.fill(d, INF);
            d[r]=0;
            int count=0;
            while(true) {
                boolean update =false;
                for(int i=0;i<E;i++) {
                    if(d[e[i].from]!=INF&&d[e[i].from]+e[i].cost<d[e[i].to]) {
                        update=true;
                        d[e[i].to]=d[e[i].from]+e[i].cost;
                    }
                }
                if(!update)break;
                if(count==V) {
                    p("NEGATIVE CYCLE");
                    return null;
                }
                count++;
            }
            return d;
        }
        //最小全域木問題(クラスカル法)
        long kruskal(int V,edge es[]) {
            unionFind uf = new unionFind(V);
            Arrays.sort(es);
            long res=0;
            for (int i = 0; i < es.length; i++) {
                if(uf.find( es[i].from)!=uf.find( es[i].to)) {
                    uf.union(es[i].from, es[i].to);
                    res+=es[i].cost;
                }
            }
            return res;
        }
    }
    private static long Pow(long i,long t) {
        //iのt乗をO(log t)で返す
        long a=i;
        long res=1;
        //for(int i=0;i<S.length();i++) {if(S.charAt(N-i)=='1') {res=res*a%mod;}
        //tをStringで受け取りたい時用
        while(t!=0) {
            if((1&t)==1) {
                res=res*a;
            }
            a=a*a;
            t=t>>1;
        }
        return res;
    }
    private static Map<Long, Integer> primeNumbers(long N) {//素因数列挙
        Map<Long, Integer> c = new HashMap<>();
        for(long i=2;i*i<=N;i++) {
            if(N%i==0) {
                int count=0;
                while(N%i==0) {
                    N/=i;
                    count++;
                }
                c.put(i, count);
                continue;
            }
        }
        if(N!=1) {
            c.put(N, 1);
        }
        return c;
    }
//=========================Union Find=============================================
    //union idx2 tree to idx1 tree O(a(N))
static class unionFind{
    int UNI[],n;
    public unionFind(int N) {
        // TODO 自動生成されたコンストラクター・スタブ
        n=N;
        init();
    }
    void init() {
        UNI=new int[n];
        for (int i = 0; i < n; i++) {
            UNI[i]=i;
        }
    }
    int get(int idx) {
        return UNI[idx];
    }
    int find(int idx) {//木の根のindexを返す
        if(UNI[idx]==idx) return idx;
        return UNI[idx] = find(UNI[idx]);
    }
     void shape() {//木の根に直接つなげる 経路圧縮
        for(int i=0;i<n;i++) {
            find(i);
        }
    }
    void union(int idx1,int idx2) {//idx1の根にidx2をつなげる
        int root1 = find(idx1);
        int root2 = find(idx2);
        UNI[root2] = root1;
    }
   int MaxSize() {//最も大きい木の頂点数を返す
        shape();
        int V[]=new int[n];
        int max=0;
        for(int i=0;i<n;i++) {
            V[UNI[i]]++;
            max=Math.max(max, V[UNI[i]]);
        }
        return max;
    }
    int sum() {//木の数を返す
        int res=0;
        for(int i=0;i<n;i++) {
            if(UNI[i]==i)res++;
        }
        return res;
    }
    void union2(int tree[],int idx1,int idx2) {//idx1の根にidx2をつなげる
        int root1 = find(idx1);
        int root2 = find(idx2);
        if(root1==root2)return;
        if(c.get(root1).size()>c.get(root2).size()) {
            //root2をroot1に移し替える
            for(int a:c.get(root2).keySet()) {
                if(!c.get(root1).containsKey(a)) {
                    c.get(root1).put(a, 0);
                }
                c.get(root1).replace(a, c.get(root1).get(a)+c.get(root2).get(a));
            }
            tree[root2] = root1;
        }else {
            for(int a:c.get(root1).keySet()) {
                if(!c.get(root2).containsKey(a)) {
                    c.get(root2).put(a, 0);
                }
                c.get(root2).replace(a, c.get(root2).get(a)+c.get(root1).get(a));
            }
            tree[root1] = root2;
        }
    }
}
//=========================二分探索=============================================
private static class binarySerch{
    public binarySerch() {
        // TODO 自動生成されたコンストラクター・スタブ
    }
    int BinarySearch(int A[],int value) {
        int S=0,E=A.length,G=-1;
        while(S<=E) {
            G=(S+E)/2;
            if(A[G]==value)return G;
            else if(A[G]>value) {
                if(E==G)break;E=G;
            }else if(A[G]<value) {
                if(S==G)break;S=G;
            }
        }
        return -1;
    }
    int lowerBound(int A[],int value) {
        //A[i-1]<value<=A[i] value以上のindexを返す
        //value未満しかなかったらA.lengthを返す
        //value以上の個数は(A.length-i)value未満の個数はiである
        int S=0,E=A.length,G=-1;
        if(A[0]>=value)return 0;
        if(A[A.length-1]<value)return A.length;
        while(true) {
            G=(S+E)/2;
            if(A[G]>=value&&A[G-1]<value) {
                return G;
            }else if(A[G]>=value) {
                E=G;
            }else if(A[G]<value) {
                S=G;
            }
        }
    }
    int upperBound(int A[],int value) {
        //A[i-1]<=value<A[i] valueより大きい数のindexの最小値を返す
        //value以下しかなかったらA.lengthを返す
        //valueより大きい数の個数は(A.length-i)value以下の個数はiである
        int S=0,E=A.length,G=-1;
        if(A[0]>value)return 0;
        if(A[A.length-1]<=value)return A.length;
        while(true) {
            G=(S+E)/2;
            if(A[G]>value&&A[G-1]<=value) {
                return G;
            }else if(A[G]>value) {
                E=G;
            }else if(A[G]<=value) {
                S=G;
            }
        }
    }
    int lowerBound(long A[],long value) {
        //A[i-1]<value<=A[i] value以上の最小indexを返す
        //value未満しかなかったらA.lengthを返す
        //value以上の個数は(A.length-i)value未満の個数はiである
        int S=0,E=A.length,G=-1;
        if(A[0]>=value)return 0;
        if(A[A.length-1]<value)return A.length;
        while(true) {
            G=(S+E)/2;
            if(A[G]>=value&&A[G-1]<value) {
                return G;
            }else if(A[G]>=value) {
                E=G;
            }else if(A[G]<value) {
                S=G;
            }
        }
    }
    int upperBound(long A[],long value) {
        //A[i-1]<=value<A[i] valueより大きい数のindexの最小値を返す
        //value以下しかなかったらA.lengthを返す
        //valueより大きい数の個数は(A.length-i)value以下の個数はiである
        int S=0,E=A.length,G=-1;
        if(A[0]>value)return 0;
        if(A[A.length-1]<=value)return A.length;
        while(true) {
            G=(S+E)/2;
            if(A[G]>value&&A[G-1]<=value) {
                return G;
            }else if(A[G]>value) {
                E=G;
            }else if(A[G]<=value) {
                S=G;
            }
        }
    }
    int lowerBound(ArrayList<Integer> A,int value) {
        //A[i-1]<value<=A[i] value以上のindexを返す
        //value未満しかなかったらA.lengthを返す
        //value以上の個数は(A.length-i)value未満の個数はiである
        int S=0,E=A.size(),G=-1;
        if(A.get(0)>=value)return 0;
        if(A.get(A.size()-1)<value)return A.size();
        while(true) {
            G=(S+E)/2;
            if(A.get(G)>=value&&A.get(G-1)<value) {
                return G;
            }else if(A.get(G)>=value) {
                E=G;
            }else if(A.get(G)<value) {
                S=G;
            }
        }
    }
    int upperBound(ArrayList<Integer> A,int value) {
        //A[i-1]<=value<A[i] valueより大きい数のindexの最小値を返す
        //value以下しかなかったらA.lengthを返す
        //valueより大きい数の個数は(A.length-i)value以下の個数はiである
        int S=0,E=A.size(),G=-1;
        if(A.get(0)>value)return 0;
        if(A.get(A.size()-1)<=value)return A.size();
        while(true) {
            G=(S+E)/2;
            if(A.get(G)>value&&A.get(G-1)<=value) {
                return G;
            }else if(A.get(G)>value) {
                E=G;
            }else if(A.get(G)<=value) {
                S=G;
            }
        }
    }
    int lowerBound(ArrayList<Long> A,long value) {
        //A[i-1]<value<=A[i] value以上のindexを返す
        //value未満しかなかったらA.lengthを返す
        //value以上の個数は(A.length-i)value未満の個数はiである
        int S=0,E=A.size(),G=-1;
        if(A.get(0)>=value)return 0;
        if(A.get(A.size()-1)<value)return A.size();
        while(true) {
            G=(S+E)/2;
            if(A.get(G)>=value&&A.get(G-1)<value) {
                return G;
            }else if(A.get(G)>=value) {
                E=G;
            }else if(A.get(G)<value) {
                S=G;
            }
        }
    }
    int upperBound(ArrayList<Long> A,long value) {
        //A[i-1]<=value<A[i] valueより大きい数のindexの最小値を返す
        //value以下しかなかったらA.lengthを返す
        //valueより大きい数の個数は(A.length-i)value以下の個数はiである
        int S=0,E=A.size(),G=-1;
        if(A.get(0)>value)return 0;
        if(A.get(A.size()-1)<=value)return A.size();
        while(true) {
            G=(S+E)/2;
            if(A.get(G)>value&&A.get(G-1)<=value) {
                return G;
            }else if(A.get(G)>value) {
                E=G;
            }else if(A.get(G)<=value) {
                S=G;
            }
        }
    }
}
    private static long modNcR2(int n,int r,int mod) {
        if(r<0||n<r)return 0;
        long N=kaijou(n, mod);
        long Nr=kaijou(n-r, mod);
        long R=kaijou(r, mod);
        return (((N*modPow(Nr, mod-2, mod))%mod)*modPow(R, mod-2, mod))%mod;
        // n!/(n-r)!/r!
    }
    private static long modPow(long i,long t,long mod) {
        if(t==0)return 1%mod;
        if(i==0||t<0)return 0;//0未満乗は未定義で
        //iのt乗をO(log t)で返す
        i%=mod;
        long a=i;
        long res=1;
        //for(int i=0;i<S.length();i++) {if(S.charAt(N-i)=='1') {res=res*a%mod;}
        //tをbitのStringで受け取った時用？
        while(t!=0) {
            if((1&t)==1) {
                res=res*a%mod;
            }
            a=a*a%mod;
            t=t>>1;
        }
        return res;
    }
    private static long min(long ...a) {
        long m=a[0];
        for(int i=0;i<a.length;i++) {
            m=Math.min(a[i], m);
        }
        return m;
    }
    private static int min(int ...a) {
    int m=a[0];
    for(int i=0;i<a.length;i++) {
        m=Math.min(a[i], m);
    }
    return m;
}
    private static int max(int ...a) {
    int m=a[0];
    for(int i=0;i<a.length;i++) {
        m=Math.max(a[i], m);
    }
    return m;
}
    private static long max(long ...a) {
        long m=a[0];
        for(int i=0;i<a.length;i++) {
            m=Math.max(a[i], m);
        }
        return m;
    }
    private static double min(double ...a) {
        double m=a[0];
    for(int i=0;i<a.length;i++) {
        m=Math.min(a[i], m);
    }
    return m;
}
    private static double max(double ...a) {
    double m=a[0];
    for(int i=0;i<a.length;i++) {
        m=Math.max(a[i], m);
    }
    return m;
}
    private static int abs(int a) {
        return max(a,-a);
    }
    private static long abs(long a) {
        return max(a,-a);
    }
    private static double abs(double a) {
        return max(a,-a);
    }
    private static String zeroume(String S,int V) {
        while(S.length()<V)S='0'+S;
        return S;
    }
    //速度が足りないときは、前計算を1回だけにしたり、longをintに変えたりするといい
    //エラストネスの篩風のやつもあり
    private static long gcd(long ...nums) {
        long res=0;
        for (int i = 0; i < nums.length; i++) {
            res=gcd(res,nums[i]);
        }
        return res;
    }
    private static long lcm(long ...nums) {
        long res=1;
        for (int i = 0; i < nums.length; i++) {
            res=lcm(res,nums[i]);
        }
        return res;
    }
    public static long gcd(long num1,long num2) {
        if(num2==0) return num1;
        else return gcd(num2,num1%num2);
    }
    public static long lcm(long num1,long num2) {
        return num1*num2/gcd(num1,num2);
    }
    //O(N^0.5)
        private static void bubunwa() {
        int N=sc.nextInt();
        int K=sc.nextInt();
        int a[]=sc.nextIntArray(N, false);
        boolean dp[] =new boolean[K+1];
        Arrays.fill(dp, false);
        dp[0]=true;
        for(int i=0;i<N;i++) {
            for(int x=K-a[i];x>=0;x--) {
                if(dp[x])dp[x+a[i]]=true;
            }
        }
        p(dp[K] ? "Yes":"No");
    }
    static String nextPermutation(String s) {
        ArrayList<Character> list=new ArrayList<Character>();
        for(int i=0;i<s.length();i++) {
            list.add(s.charAt(i));
        }
        int pivotPos=-1;
        char pivot=0;
        for(int i=list.size()-2;i>=0;i--) {
            if(list.get(i)<list.get(i+1)) {
                pivotPos=i;
                pivot=list.get(i);
                break;
            }
        }
        if(pivotPos==-1&&pivot==0) {
            return "Final";
        }
        int L=pivotPos+1,R=list.size()-1;
        int minPos=-1;
        char min =Character.MAX_VALUE;
        for(int i=R;i>=L;i--) {
            if(pivot<list.get(i)) {
                if(list.get(i)<min) {
                    min=list.get(i);
                    minPos=i;
                }
            }
        }
        Collections.swap(list, pivotPos, minPos);
        Collections.sort(list.subList(L, R+1));
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<list.size();i++) {
            sb.append(list.get(i));
        }
        return sb.toString();
    }
    private static long[][] com;
    private static void nCr(int mod) {
    int MAX = 3001;
    com= new long[MAX][MAX];
    for(int i = 0; i < MAX; i++)
        com[i][0] = 1;
    for(int i = 1; i < MAX; i++) {
        for(int j = 1; j <= i; j++) {
            com[i][j] = com[i-1][j-1] + com[i-1][j];
            com[i][j] %= mod;
        }
    }
}
    //https://qiita.com/p_shiki37/items/65c18f88f4d24b2c528b より
    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
          if (ptr < buflen) {
            return true;
          } else {
            ptr = 0;
            try {
              buflen = in.read(buffer);
            } catch (IOException e) {
              e.printStackTrace();
            }
            if (buflen <= 0) {
              return false;
            }
          }
          return true;
        }
        private int readByte() {
          if (hasNextByte()) return buffer[ptr++];
          else return -1;
        }
        private static boolean isPrintableChar(int c) {
          return 33 <= c && c <= 126;
        }
        private void skipUnprintable() {
          while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
        }
        public boolean hasNext() {
          skipUnprintable();
          return hasNextByte();
        }
        public String next() {
          if (!hasNext()) throw new NoSuchElementException();
          StringBuilder sb = new StringBuilder();
          int b = readByte();
          while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
          }
          return sb.toString();
        }
        public long nextLong() {
          if (!hasNext()) throw new NoSuchElementException();
          long n = 0;
          boolean minus = false;
          int b = readByte();
          if (b == '-') {
            minus = true;
            b = readByte();
          }
          if (b < '0' || '9' < b) {
            throw new NumberFormatException();
          }
          while (true) {
            if ('0' <= b && b <= '9') {
              n *= 10;
              n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
              return minus ? -n : n;
            } else {
              throw new NumberFormatException();
            }
            b = readByte();
          }
        }
        public int nextInt() {
          return (int) nextLong();
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
        public int[] nextIntArray(int N) {
                int[] array = new int[N];
                for (int i = 0; i < N; i++) {
                  array[i] = sc.nextInt();
                }
                return array;
            }
        public int[] nextIntArray(int N, boolean oneBased) {
          if (oneBased) {
            int[] array = new int[N + 1];
            for (int i = 1; i <= N; i++) {
              array[i] = sc.nextInt();
            }
            return array;
          } else {
            int[] array = new int[N];
            for (int i = 0; i < N; i++) {
              array[i] = sc.nextInt();
            }
            return array;
          }
        }
        public long[] nextLongArray(int N, boolean oneBased) {
          if (oneBased) {
            long[] array = new long[N + 1];
            for (int i = 1; i <= N; i++) {
              array[i] = sc.nextLong();
            }
            return array;
          } else {
            long[] array = new long[N];
            for (int i = 0; i < N; i++) {
              array[i] = sc.nextLong();
            }
            return array;
          }
        }
        public long[] nextLongArray(int N) {
                long[] array = new long[N];
                for (int i = 0; i < N; i++) {
                  array[i] = sc.nextLong();
                }
                return array;
              }
        public long[][]nextLongDimensionalArray(int H,int W) {
            long[][] array = new long[H][W];
            for (int i = 0; i < H; i++) {
              array[i] =sc.nextLongArray(W);
            }
            return array;
            }
            public int[][]nextIntDimensionalArray(int H,int W) {
                int[][] array = new int[H][W];
                for (int i = 0; i < H; i++) {
                  array[i] =sc.nextIntArray(W);
                }
                return array;
                }
            public String[] nextArray(int N) {
                String[] array = new String[N];
                for (int i = 0; i < N; i++) {
                  array[i] = sc.next();
                }
                return array;
              }
            public String[][]nextDimensionalArray(int H,int W) {
                String[][] array = new String[H][W];
                for (int i = 0; i < H; i++) {
                  array[i] =sc.nextArray(W);
                }
                return array;
                }
            public double[] nextDoubleArray(int N) {
                double[] array = new double[N];
                for (int i = 0; i < N; i++) {
                  array[i] = sc.nextDouble();
                }
                return array;
              }
      }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0