/* created by krps 本体は120行目あたりの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.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; public class Main { public static void main(String[] args) { for(int i=0;i<1;i++) { slover(); out.flush(); } } static FastScanner sc = new FastScanner(); static PrintWriter out = new PrintWriter(System.out); //Set a=new HashSet(); //Integer.toBinaryString(i); //Integer.toString(i, 2); // //Integer.parseInt(bin, 2); //bitset //StringBuffer S = new StringBuffer(sc.next()); //String hoge2 = str.reverse().toString(); //map.containsKey(A) //Map map = new HashMap(N); /*for ( キーのデータ型 key : マップの名前.keySet() ) { データのデータ型 data = マップの名前.get( key ); // keyやdataを使った処理; }*/ //int i = Integer.parseInt(s); //Queue qq=new ArrayDeque<>(); //add,poll,peek BFSは前から実行される //Deque dd=new ArrayDeque<>();//push後ろに入れる,poll(pop)後ろからとる,peek addは先頭に入るからバグ注意 //stackdfsは後ろから実行される //ArrayList cc = new ArrayList<>(N); //cc.contains(tmp) //Arrays.asList(c).contains("a") //list.set(1,"walk");//1 1 2 3 5 //PriorityQueue r=new PriorityQueue();//add poll public static class Pair extends AbstractMap.SimpleEntry implements Comparable> { public Pair(final K key, final V value) { super(key, value); } @Override public int compareTo(Pair 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 long mod=1000000007; //private static long mod2=998244353; private static int INF =999999999; @SuppressWarnings("unused") private static long LINF=4000000000000000000L; 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; } private static ArrayList Divisors(long t) { ArrayList c=new ArrayList(); for(long i=1;i*i<=t;i++) { if(t%i==0) { if(i*i!=t) { c.add(t/i); } c.add((long)i); } } return c; } private static ArrayList sortedfacto(long t) { ArrayList c=new ArrayList(); for(long i=2;i*i<=t;i++) { if(t%i==0) { p(t+" "+i); c.add((long)i); t/=i; i--; } } if(t!=1)c.add(t); Collections.sort(c); return c; } @SuppressWarnings("unused") private static long ncr(long n,long r) { long res=1; for(int i=0;i=0) { //p(t); res++; t=T.indexOf(v,t)+1; } return res; } private static int arrayMax(int a[]) { int res=0; for(int i=0;i> map = new HashMap<>(); // private static int ketawa(String S) { int res=0; for(int i=0;i void p(T t) {out.println(t);} private static 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 int mod=1000000000+7; private static long A_[]; private static long memo[][]; private static ArrayList> c; private static int[] ArrayListToList(ArrayList c2,int[] v) {for(int i=0;i ListToArrayList(int[] v) {ArrayList c=new ArrayList<>(v.length);for(int i=0;i=k-1; i++) { res+=V(N-i,k-1); } return memo2[N][k]=res; } } private static class segmentTree{ private static int maxN=1<<19,n; private static long dat[]=new long[2*maxN-1]; private static long tannigen=-1; static void init(int n_) { n=1; while(n0) { k=(k-1)/2; dat[k]=monoid(dat[k*2+1],dat[k*2+2]); } toString(3); } static long get(int k) { k+=n-1; return dat[k]; } static void toString(int n) { for(int i=0;i{ int a; int b; D(int a,int b){ this.a=a; this.b=b; } @Override public int compareTo(D o) { Comparable key = (Comparable)this.a; Comparable key2 = (Comparable)o.a; Comparable key3 = (Comparable)this.b; Comparable key4 = (Comparable)o.b; if(key.compareTo(key2)==0) { return key3.compareTo(key4); } return key.compareTo(key2); } } private static int getCycle(int a,int d) { // a/dの循環小数を求める //小さいNならごり押しで試せるからそれで検証しよう long V=1; long mod=1; //int A[] = new int[d+1]; Map m = new HashMap<>(); //String S=""; //String G=""; int res=0; while(true) { V=(mod*10)/d; if(!m.containsKey(mod))m.put(mod, 0); if(m.get(mod)>=2)break; //if(A[mod]==0)G+=V; if(m.get(mod)==1)res++;//S+=V; //A[mod]+=1; m.replace(mod, m.get(mod)+1); mod=(mod*10)%d; } return res; //if(G.lastIndexOf(S)<0) { // String x[]={G,S}; // return x; //} //G=G.substring(0,G.lastIndexOf(S)); //p(d+" "+G+" "+S+" "+(double)a/d); //p("end"); ///S=S.substring(1,S.length())+S.charAt(0); //String x[]={G,S}; //return x; } private static void slover(){ int T = sc.nextInt(); for(int p=0;p dikstr2(int V,int E,int r,Map> m) { //最短距離を配列ではなく、mapで処理したい Map D = new HashMap<>(V); for (int i:m.keySet()) { D.put(i, LINF); } D.replace(r, 0L); PriorityQueue> p = new PriorityQueue<>();//add poll p.add(new Pair(0L, r)); while(!p.isEmpty()) { Pair x=p.poll(); int from=x.getValue(); if(x.getKey()>D.get(from))continue; if(!m.containsKey(from))continue; for (int i = 0; i < m.get(from).size(); i++) { graph.edge2 e=m.get(from).get(i); if(D.get(e.to)>D.get(from)+e.cost) { D.replace(e.to, D.get(from)+e.cost); p.add(new Pair(D.get(e.to), e.to)); } } } return D; } private static class graph{ static class edge implements Comparable{ 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; public edge2(int to,long cost) { this.to=to; this.cost=cost; } } //単一始点最短距離問題(ダイクストラ法) 負閉路対策不可 経路復元 private static long[] dikstr(int V,int E,int r,Map> m) { //int path[]=new int[V]; //Arrays.fill(path, -1); long d[]=new long[V]; Arrays.fill(d, LINF); d[r]=0; PriorityQueue> p = new PriorityQueue<>();//add poll p.add(new Pair(0L, r)); while(!p.isEmpty()) { Pair 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(d[e.to], e.to)); //path[e.to]=from; } } } //経路復元 //複数の経路を考える必要がある時は、pathに複数の同じような最短経路の辺を保存しておく //ArrayList 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; } //単一始点最短距離問題(ベルマンフォード法) 負閉路対策済み private static int[] shortest_path(int V,int E,int r,edge e[]) { int d[]=new int[V]; //0~eのグラフはこれ //Map d = new HashMap<>();それ以外はこれ //for(int i=0;i(e[i].to, INF)); // if(!d.containsKey(e[i].from))m.add(new Pair(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>1; } return res; } private static Map primeNumbers(long N) { Map 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)) private static class Union_Find{ private static int find(int[] tree,int idx) {//木の根のindexを返す if(tree[idx]==idx) return idx; return tree[idx] = find(tree,tree[idx]); } private static void union_shape(int[] tree) {//木の根に直接つなげる 経路圧縮 for(int i=0;ic.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; } //return tree; } } //=========================二分探索============================================= private static class binarySerch{ private static 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)return 0; if(A[A.length-1]=value&&A[G-1]=value) { E=G; }else if(A[G]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; } } } private static int lowerBound(long A[],long value) { //A[i-1]=value)return 0; if(A[A.length-1]=value&&A[G-1]=value) { E=G; }else if(A[G]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; } } } private static int lowerBound(ArrayList A,int value) { //A[i-1]=value)return 0; if(A.get(A.size()-1)=value&&A.get(G-1)=value) { E=G; }else if(A.get(G) A,int value) { //A[i-1]<=valuevalue)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 int lowerBound(ArrayList A,long value) { //A[i-1]=value)return 0; if(A.get(A.size()-1)=value&&A.get(G-1)=value) { E=G; }else if(A.get(G) A,long value) { //A[i-1]<=valuevalue)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 class cumlativeSum{ private static long GetCumulativeSum(long V[],int a,int b,int nindex) { //1-indexであるa-b間の和を求める 要素の数はa-b+1個 if(nindex==0) {//0-indexの時は1-indexに変える a++;b++; } return V[b]-V[a-1]; } private static int GetCumulativeSum(int V[],int a,int b,int nindex) { //1-indexであるa-b間の和を求める 要素の数はa-b+1個 if(nindex==0) {//0-indexの時は1-indexに変える a++;b++; } return V[b]-V[a-1]; } private static int[] nextIntCumulativeSum(int N) { int Csum[]=new int[N+1]; for(int i=1;i<=N;i++) { Csum[i]=sc.nextInt()+Csum[i-1]; } return Csum; } private static long[] nextLongCumulativeSum(int N) { long Csum2[]=new long[N+1]; for(int i=1;i<=N;i++) { Csum2[i]=sc.nextInt()+Csum2[i-1]; } return Csum2; } private static int getV(int S[][],int x,int y,int a,int b) { //p(S[x-1][y-1]+" "+S[x+a-1][y+b-1]+" "+S[x-1][y+b-1]+" "+S[x+a-1][y-1]); return S[x-1][y-1]+S[x+a-1][y+b-1]-S[x-1][y+b-1]-S[x+a-1][y-1]; } } private static long modNcR2(int n,int r,int mod) { long x_b=1; for(int i=0;i>1; } return res; } private static long min(long ...a) { long m=a[0]; for(int i=0;i=0;x--) { if(dp[x])dp[x+a[i]]=true; } } p(dp[K] ? "Yes":"No"); } static String nextPermutation(String s) { ArrayList list=new ArrayList(); for(int i=0;i=0;i--) { if(list.get(i)=L;i--) { if(pivot