import java.util.*; import java.io.*; class Main{ public static void solve(Read br,Write out){ //out.debug=true; int t=br.readI(); for(int tt=0;ttb ? 1 : a n){ Collections.sort(n); } public static void sortD(ArrayList n){ Collections.sort(n,Collections.reverseOrder()); } public static void sortA(int n[][],int k){ Arrays.sort(n,(a, b) -> Integer.compare(a[k], b[k])); } public static void sortD(int n[][],int k){ Arrays.sort(n,(a, b) -> Integer.compare(b[k], a[k])); } public static void mysort(int n[][],int k){ Arrays.sort(n, new Comparator(){ public int compare(int[] x,int[] y){ if(x[k]==y[k]){ return x[1]-y[1]; } return x[k]-y[k]; } }); } static class ModFunc{ int n; long mod; long fact[],invfact[]; public ModFunc(int n,long mod){ this.n=n;this.mod=mod; fact=new long[n+1];invfact=new long[n+1]; modfact();modinvfact(); } public static long modfact(int n,long mod){ long k=1; for(int i=1;i<=n;i++){ k = k*i % mod; } return k; } public static long modinvfact(int n,long mod){ return modinv(modfact(n,mod),mod); } public static long modinv(long a,long mod){ long x1=1,x2=0; long p=mod,q,t; while(a%p!=0){ q = a/p; t = x1-q*x2; x1=x2; x2=t; t=a%p; a=p; p=t; } return x2<0 ? x2+mod : x2; } private void modfact(){ fact[0]=1; for(int i=1;i<=n;i++){ fact[i] = fact[i-1]*i % mod; } } private void modinvfact(){ invfact[n]=modinv(fact[n],mod); for(int i=n-1;i>=0;i--){ invfact[i] = invfact[i+1]*(i+1) % mod; } } public long modConv(int n,int k){ return ((fact[n]*invfact[n-k])%mod)*invfact[k]%mod; } public static long modpow(long x,long n,long pow){ long r = 1; while(n>=1){ if(1==(n&1)){ r = r*x % pow; } x = x*x % pow; n/=2; } return r; } } static class Permu{ int n; public int a[]; boolean flg; public Permu(int n){ this.n=n;flg=true; a=new int[n]; for(int i=0;i=0;i--){ if (a[i]=0;i--){ if (a[i]>a[i+1]){ for (int j=n-1;;j--){ if (a[i] > a[j]){ int temp=a[i]; a[i]=a[j]; a[j] = temp; i++; for (j=n-1;i a; HashMap map; public Compress(int[]b){ HashSet temp = new HashSet<>(); for(int i:b){ temp.add(i); } a=new ArrayList(temp); setup(); } public Compress(ArrayListb){ a=new ArrayList(new HashSet(b)); setup(); } private void setup(){ map = new HashMap<>(); sortA(a); for(int i=0;i0){ now = (now-1)/2; ar[now] = func(ar[now*2+1],ar[now*2+2]); } } public void add(int i,int x){ update(i,ar[i+leafN-1]+x); } public int get(int i){ return ar[i+leafN-1]; } public int query(int a,int b){ return query(a,b,0,0,leafN); } public int query(int a,int b,int k,int l,int r){ if(r<=a||b<=l){ return temp; }else if(a<=l&&r<=b){ return ar[k]; } int t1=query(a,b,k*2+1,l,(l+r)/2),t2=query(a,b,k*2+2,(l+r)/2,r); return func(t1,t2); } private int twon(int x){ int i=1; while(i0;ii-=(ii&-ii)){ k+=ar[ii]; } return k; } private int twon(int x){ int i=1; while(i> g; public Graph(int nn){ n=nn; g=new ArrayList>(); for(int i=0;i()); } } public void add(int a,int b,int d){ g.get(a).add(new Edge(b,d)); g.get(b).add(new Edge(a,d)); } public void addY(int a,int b,int d){ g.get(a).add(new Edge(b,d)); } public void add(int a,int b){ g.get(a).add(new Edge(b,1)); g.get(b).add(new Edge(a,1)); } public void addY(int a,int b){ g.get(a).add(new Edge(b,1)); } public int len(int a){ return g.get(a).size(); } public int[] dijkstra(int s){ int dist[]=new int[n]; for(int i=0;i q = new PriorityQueue(new Comparator(){ public int compare(int[] a, int[] b) { return a[1]-b[1]; } }); q.add(new int[]{s,0}); while(q.size()>0){ int[] p = q.poll(); if(dist[p[0]]!=p[1]){continue;} for(Edge e:g.get(p[0])){ if(dist[e.v]>dist[p[0]]+e.d){ dist[e.v]=dist[p[0]]+e.d; q.add(new int[]{e.v,dist[e.v]}); } } } return dist; } public void dfs(int v){dfs(v,new boolean[n]);} private void dfs(int v,boolean flg[]){ flg[v]=true; for(Edge e:g.get(v)){ if(!flg[e.v]){ dfs(e.v,flg); } } } public void bfs(int s){ boolean flg[]=new boolean[n]; Queue q = new ArrayDeque(); q.add(s); while(q.size()>0){ int v = q.poll(); flg[v]=true; for(Edge e:g.get(v)){ if(!flg[e.v]){ q.add(e.v); flg[e.v]=true; }}} } public int minspantree(){ PriorityQueue q = new PriorityQueue(new Comparator(){ public int compare(Edge a, Edge b) { return a.d-b.d; } }); boolean flg[]=new boolean[n]; int c=1,sum=0; for(Edge e:g.get(0)){ q.add(e); } flg[0]=true; while(c list = new ArrayList(); boolean flg[]=new boolean[n]; for(int i=0;ilist){ boolean flg[]=new boolean[n]; int ren[]=new int[n]; int num=0; for(int i=n-1;i>=0;i--){ int now = list.get(i); if(!flg[now]){ dfs_scc2(now,flg,ren,num); num++; } } return ren; } private void dfs_scc(int v,boolean flg[],ArrayListlist){ flg[v]=true; for(Edge e:g.get(v)){ if(!flg[e.v]){ dfs_scc(e.v,flg,list); } } list.add(v); } private void dfs_scc2(int v,boolean flg[],int num[],int now){ flg[v]=true; num[v]=now; for(Edge e:g.get(v)){ if(!flg[e.v]){ dfs_scc2(e.v,flg,num,now); } } } static class Edge{ int v,d; public Edge(int v,int d){ this.v=v;this.d=d; } } } static class Read{ BufferedReader br; public Read(){ br = new BufferedReader(new InputStreamReader(System.in)); } private boolean canprint(int a){ return 33<=a&&a<=126; } private int skipread(){ int a=readC(); while(a!=-1&&!canprint(a)){ a=readC(); } return a; } public char readC(){ try{ return (char)br.read(); }catch(IOException e){ e.printStackTrace(); return (char)-1; } } public String readLine(){ try{ return br.readLine(); }catch(IOException e){ e.printStackTrace(); return ""; } } public String readS(){ StringBuilder sb = new StringBuilder(); int k = skipread(); while(true){ if(!canprint(k)){break;} sb.append((char)k); k = readC(); } return sb.toString(); } public int readI(){ int r = 0; int k = skipread(); int flg = 1; if(k=='-'){ flg=-1; k=readC(); } while(true){ if(!canprint(k)){break;} r = r*10+(k-'0'); k = readC(); } return flg*r; } public long readL(){ long r = 0; int k = skipread(); int flg = 1; if(k=='-'){ flg=-1; k=readC(); } while(true){ if(!canprint(k)){break;} r = r*10+(k-'0'); k = readC(); } return flg*r; } public String[] readSs(int n){ String[]a = new String[n]; for(int i=0;ivoid pr(T str){ out.print(str); } public void pl(T str){ out.println(str); } public void pr(int[]a){ int t=a.length; if(t>0){pr(a[0]);} for(int i=1;i0){pr(a[0]);} for(int i=1;i0){pr(a[0]);} for(int i=1;ivoid prA(T str){ System.out.print(str); } public static void plA(T str){ System.out.println(str); } public static void prA(int[]a){ int t=a.length; if(t>0){prA(a[0]);} for(int i=1;i0){prA(a[0]);} for(int i=1;i0){prA(a[0]);} for(int i=1;ivoid debugP(T str){ if(debug){ pl(str); } } } public static long stol(String s){ return Long.parseLong(s); } public static int stoi(String s){ return Integer.parseInt(s); } public static int[] stoi(String s[]){ int a[]=new int[s.length]; for(int i=0;i