#681987 (Java21) No.1620 Substring Sum

提出ソース
結果

問題	No.1620 Substring Sum
ユーザー	kps
提出日時	2021-07-22 22:43:08
言語	Java21 (openjdk 21)
結果	AC
実行時間	122 ms / 2,000 ms
コード長	52,466 bytes
コンパイル時間	4,021 ms
コンパイル使用メモリ	104,792 KB
実行使用メモリ	52,388 KB
最終ジャッジ日時	2024-07-17 19:03:58
合計ジャッジ時間	6,074 ms
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	48 ms 50,556 KB
testcase_01	AC	47 ms 50,712 KB
testcase_02	AC	46 ms 50,680 KB
testcase_03	AC	48 ms 50,440 KB
testcase_04	AC	122 ms 51,784 KB
testcase_05	AC	109 ms 52,104 KB
testcase_06	AC	109 ms 52,064 KB
testcase_07	AC	109 ms 52,388 KB
testcase_08	AC	109 ms 52,056 KB
testcase_09	AC	109 ms 52,344 KB
testcase_10	AC	109 ms 52,292 KB
testcase_11	AC	105 ms 52,032 KB
testcase_12	AC	81 ms 51,760 KB
testcase_13	AC	109 ms 52,196 KB
testcase_14	AC	103 ms 52,316 KB
testcase_15	AC	103 ms 52,140 KB
testcase_16	AC	92 ms 52,312 KB
testcase_17	AC	105 ms 52,112 KB
testcase_18	AC	47 ms 50,640 KB
testcase_19	AC	57 ms 50,380 KB
testcase_20	AC	107 ms 52,244 KB
testcase_21	AC	107 ms 51,872 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
/*
 	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() {
		String S = sc.next();
		int V[]=new int[S.length()];
		for (int i = 0; i < S.length(); i++) {
			V[i]=S.charAt(i)-'0';
		}
		long mod=998244353;
		long A=1;
		long SUM=0;
		long a=modPow(2, S.length()-1, mod);
		for (int i = V.length-1;i>=0;i--) {
			SUM+=((V[i]*a)%mod)*A;
			SUM%=mod;
			A=A+10*A;
			A%=mod;
			a*=modinv(2, mod);
			a%=mod;
		}
		System.out.println(SUM);
		
		
		
		
	}
	/*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;
		      }
	  }


}
yukicoder

結果

テストケース

ソースコード
