import java.io.IOException; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.NoSuchElementException; import java.util.Objects; import java.util.PriorityQueue; import java.util.Queue; import java.util.Random; import java.util.Scanner; import java.util.Set; import java.util.Stack; import java.util.TreeMap; import java.util.TreeSet; import java.util.function.BiFunction; public class Main{ static Scanner scn = new Scanner(System.in); static FastScanner sc = new FastScanner(); static Mathplus mp = new Mathplus(); static PrintWriter ot = new PrintWriter(System.out); static Random rand = new Random(); static StringManager sm = new StringManager(" "); static int mod = 1000000007; static long modmod = (int)mod * mod; static long inf = (long)1e17; static int[] dx = {0,1,0,-1}; static int[] dy = {1,0,-1,0}; static int[] dx8 = {-1,-1,-1,0,0,1,1,1}; static int[] dy8 = {-1,0,1,-1,1,-1,0,1}; static char[] dc = {'R','D','L','U'}; static String sp = " "; public static void main(String[] args) { int N = sc.nextInt(); int ans = 0; for(int i=0;i set; int size; long sum; MultiHashSet(){ set = new HashMap(); size = 0; sum = 0; } void add(int e){ if(set.containsKey(e))set.put(e,set.get(e)+1); else set.put(e,1); size++; sum += e; } void remove(int e) { set.put(e,set.get(e)-1); if(set.get(e)==0)set.remove(e); size--; sum -= e; } boolean contains(int e) { return set.containsKey(e); } boolean isEmpty() { return set.isEmpty(); } int count(int e) { if(contains(e))return set.get(e); else return 0; } Set keyset(){ return set.keySet(); } } class MultiSet{ TreeMap set; int size; long sum; MultiSet(){ set = new TreeMap(); size = 0; sum = 0; } void add(int e){ if(set.containsKey(e))set.put(e,set.get(e)+1); else set.put(e,1); size++; sum += e; } void remove(int e) { set.put(e,set.get(e)-1); if(set.get(e)==0)set.remove(e); size--; sum -= e; } int first() {return set.firstKey();} int last() {return set.lastKey();} int lower(int e) {return set.lowerKey(e);} int higher(int e) {return set.higherKey(e);} int floor(int e) {return set.floorKey(e);} int ceil(int e) {return set.ceilingKey(e);} boolean contains(int e) {return set.containsKey(e);} boolean isEmpty() {return set.isEmpty();} int count(int e) { if(contains(e))return set.get(e); else return 0; } MultiSet marge(MultiSet T) { if(size>T.size) { while(!T.isEmpty()) { add(T.first()); T.remove(T.first()); } return this; }else { while(!isEmpty()) { T.add(first()); remove(first()); } return T; } } Set keyset(){ return set.keySet(); } } class MultiSetL{ TreeMap set; int size; long sum; MultiSetL(){ set = new TreeMap(); size = 0; sum = 0; } void add(long e){ if(set.containsKey(e))set.put(e,set.get(e)+1); else set.put(e,1); size++; sum += e; } void remove(long e) { set.put(e,set.get(e)-1); if(set.get(e)==0)set.remove(e); size--; sum -= e; } long first() {return set.firstKey();} long last() {return set.lastKey();} long lower(long e) {return set.lowerKey(e);} long higher(long e) {return set.higherKey(e);} long floor(long e) {return set.floorKey(e);} long ceil(long e) {return set.ceilingKey(e);} boolean contains(long e) {return set.containsKey(e);} boolean isEmpty() {return set.isEmpty();} int count(long e) { if(contains(e))return set.get(e); else return 0; } MultiSetL marge(MultiSetL T) { if(size>T.size) { while(!T.isEmpty()) { add(T.first()); T.remove(T.first()); } return this; }else { while(!isEmpty()) { T.add(first()); remove(first()); } return T; } } Set keyset(){ return set.keySet(); } } class GridGraph extends Graph{ int N; int M; String[] S; HashMap map; GridGraph(int n,int m,String[] s){ super(n*m); N = n; M = m; S = s; for(int i=0;i(); for(int i=0;i> map; int[] dx = {0,1,0,-1}; int[] dy = {1,0,-1,0}; char w; char b = '#'; BetterGridGraph(int n,int m,String[] s,char[] c){ N = n; M = m; for(int i=0;i>(); for(int i=0;i()); } for(int i=0;i>(); for(int i=0;i()); } for(int i=0;i>(); for(int i=0;i()); } for(int i=0;i>(); for(int i=0;i()); } for(int i=0;i getposlist(char c) { return map.get(c); } int getpos(char c) { return map.get(c).get(0); } int[] bfs(char C) { int[] L = new int[N*M]; ArrayDeque Q = new ArrayDeque(); for(int i=0;i Q = new PriorityQueue(new IntIntComparator()); for(int i=0;iK) continue; if(L[ni][nh]==1000000007){ L[ni][nh] = L[v.b][h]+1; Q.add(new IntIntPair(nh,ni)); } } } } for(int i=0;i Q = new PriorityQueue(new IntIntComparator()); for(int i=0;iL[v] + (S[nx][ny]!='t'?S[nx][ny]-'0':0)){ L[w] = L[v] + (S[nx][ny]!='t'?S[nx][ny]-'0':0); Q.add(new IntIntPair(L[w],w)); } } } if(x%2==0) { int nx = x+1; int ny = y-1; if(X.isIn(nx)&&Y.isIn(ny)&&S[nx][ny]!=b) { int w = toint(nx,ny); if(L[w]==-1){ L[w] = L[v] + (S[nx][ny]!='t'?S[nx][ny]-'0':0); Q.add(new IntIntPair(L[w],w)); } } nx = x-1; ny = y-1; if(X.isIn(nx)&&Y.isIn(ny)&&S[nx][ny]!=b) { int w = toint(nx,ny); if(L[w]==-1){ L[w] = L[v] + (S[nx][ny]!='t'?S[nx][ny]-'0':0); Q.add(new IntIntPair(L[w],w)); } } }else { int nx = x+1; int ny = y+1; if(X.isIn(nx)&&Y.isIn(ny)&&S[nx][ny]!=b) { int w = toint(nx,ny); if(L[w]==-1){ L[w] = L[v] + (S[nx][ny]!='t'?S[nx][ny]-'0':0); Q.add(new IntIntPair(L[w],w)); } } nx = x-1; ny = y+1; if(X.isIn(nx)&&Y.isIn(ny)&&S[nx][ny]!=b) { int w = toint(nx,ny); if(L[w]==-1){ L[w] = L[v] + (S[nx][ny]!='t'?S[nx][ny]-'0':0); Q.add(new IntIntPair(L[w],w)); } } } } return L; } } class IntGridGraph{ int N; int M; int[][] B; int[] dx = {0,1,0,-1}; int[] dy = {1,0,-1,0}; BiFunction F; IntGridGraph(int n,int m,int[][] b){ N = n; M = m; B = b; } IntGridGraph(int n,int m,int[][] b,BiFunction f){ N = n; M = m; B = b; F = f; } int toint(int i,int j) { return i*M+j; } int[] bfs(int s) { int[] L = new int[N*M]; for(int i=0;i Q = new ArrayDeque(); Q.add(s); Range X = new Range(0,N-1); Range Y = new Range(0,M-1); while(!Q.isEmpty()){ int v = Q.poll(); for(int i=0;i<4;i++){ int x = v/M; int y = v%M; int nx = x+dx[i]; int ny = y+dy[i]; if(X.isIn(nx)&&Y.isIn(ny)&&F.apply(B[x][y],B[nx][ny])) { int w = toint(nx,ny); if(L[w]==-1){ L[w] = L[v] + 1; Q.add(w); } } } } return L; } void bfs(int s,int[] L) { if(L[s]!=-1) return; L[s] = 0; ArrayDeque Q = new ArrayDeque(); Q.add(s); Range X = new Range(0,N-1); Range Y = new Range(0,M-1); while(!Q.isEmpty()){ int v = Q.poll(); for(int i=0;i<4;i++){ int x = v/M; int y = v%M; int nx = x+dx[i]; int ny = y+dy[i]; if(X.isIn(nx)&&Y.isIn(ny)&&F.apply(B[x][y],B[nx][ny])) { int w = toint(nx,ny); if(L[w]==-1){ L[w] = L[v] + 1; Q.add(w); } } } } return; } int[][] bfs2(int s,int K){ int[][] L = new int[N*M][K+1]; for(int i=0;i Q = new PriorityQueue(new IntIntComparator()); Q.add(new IntIntPair(0,s)); Range X = new Range(0,N-1); Range Y = new Range(0,M-1); while(!Q.isEmpty()){ IntIntPair v = Q.poll(); for(int i=0;i<4;i++){ int x = v.b/M; int y = v.b%M; int h = v.a; int nx = x+dx[i]; int ny = y+dy[i]; if(X.isIn(nx)&&Y.isIn(ny)&&F.apply(B[x][y],B[nx][ny])) { int ni = toint(nx,ny); int nh = h + B[nx][ny]; if(nh>K) continue; if(L[ni][nh]==1000000007){ L[ni][nh] = L[v.b][h] + 1; Q.add(new IntIntPair(nh,ni)); } } } } for(int i=0;i S; static Mathplus mp; static boolean calced; static int base; static long baserev; ArrayList l; StringManager(String s){ S = new ArrayList(); for(int i=0;i(); l.add((long)S.get(0)); for(int i=1;i runlength(String s){ ArrayList ret = new ArrayList(); s += ' '; char bef = ' '; int len = 0; for(int i=0;i runlength(ArrayList s){ ArrayList ret = new ArrayList(); s.add(' '); char bef = ' '; int len = 0; for(int i=0;i l; Trie(){ l = new ArrayList(); l.add(new TrieNode()); } void add(String S,int W){ int now = 0; for(int i=0;i=S.length())return; char c = S.charAt(slook); if(n.Exist[c-'a']==-1)return; now = n.Exist[c-'a']; } } } class TrieNode{ int[] Exist = new int[26]; int weight = 0; TrieNode(){ for(int i=0;i<26;i++) { Exist[i] = -1; } } } class SizeComparator implements Comparator{ int[] size; SizeComparator(int[] s) { size = s; } public int compare(Edge o1, Edge o2) { return size[o1.to]-size[o2.to]; } } class ConvexHullTrick { long[] A, B; int len; public ConvexHullTrick(int n) { A = new long[n]; B = new long[n]; } private boolean check(long a, long b) { return (B[len - 2] - B[len - 1]) * (a - A[len - 1]) >= (B[len - 1] - b) * (A[len - 1] - A[len - 2]); } public void add(long a, long b) { while (len >= 2 && check(a, b)) { len--; } A[len] = a; B[len] = b; len++; } public long query(long x) { int l = -1, r = len - 1; while (r - l > 1) { int mid = (r + l) / 2; if (get(mid,x)>=get(mid+1,x)) { l = mid; } else { r = mid; } } return get(r,x); } private long get(int k, long x) { return A[k] * x + B[k]; } } class Range{ long l; long r; long length; Range(int L,int R){ l = L; r = R; length = R-L+1; } public Range(long L, long R) { l = L; r = R; length = R-L+1; } boolean isIn(int x) { return (l<=x&&x<=r); } long kasanari(Range S) { if(this.r{ public int compare(Range P, Range Q) { return (int) Math.signum(P.l-Q.l); } } class RightComparator implements Comparator{ public int compare(Range P, Range Q) { return (int) Math.signum(P.r-Q.r); } } class LengthComparator implements Comparator{ public int compare(Range P, Range Q) { return (int) Math.signum(P.length-Q.length); } } class SegmentTree{ int N; BiFunction f; BiFunction g; T d1; ArrayList dat; SegmentTree(BiFunction F,BiFunction G,T D1,T[] v){ int n = v.length; f = F; g = G; d1 = D1; init(n); build(v); } void init(int n) { N = 1; while(N(); } void build(T[] v) { for(int i=0;i<2*N;i++) { dat.add(d1); } for(int i=0;i=0;i--) { dat.set(i,f.apply(dat.get(i*2+1),dat.get(i*2+2))); } } void update(int k,E a) { k += N-1; dat.set(k,g.apply(dat.get(k),a)); while(k>0){ k = (k-1)/2; dat.set(k,f.apply(dat.get(k*2+1),dat.get(k*2+2))); } } T query(int a,int b, int k, int l ,int r) { if(r<=a||b<=l) return d1; if(a<=l&&r<=b) return dat.get(k); T vl = query(a,b,k*2+1,l,(l+r)/2); T vr = query(a,b,k*2+2,(l+r)/2,r); return f.apply(vl, vr); } T query(int a,int b){ return query(a,b,0,0,N); } } class LazySegmentTree extends SegmentTree{ BiFunction h; BiFunction p = (E a,Integer b) ->{return a;}; E d0; ArrayList laz; LazySegmentTree(BiFunction F,BiFunction G,BiFunction H,T D1,E D0,T[] v){ super(F,G,D1,v); int n = v.length; h = H; d0 = D0; Init(n); } void build() { } void Init(int n){ laz = new ArrayList(); for(int i=0;i<2*N;i++) { laz.add(d0); } } void eval(int len,int k) { if(laz.get(k).equals(d0)) return; if(k*2+1 dat; AddSumSegmentTree(int[] v){ int n = v.length; init(n); build(v); } void init(int n) { N = 1; while(N(); } void build(int[] v) { for(int i=0;i<2*N;i++) { dat.add(d1); } for(int i=0;i=0;i--) { dat.set(i,dat.get(i*2+1)+dat.get(i*2+2)); } } void update(int k,int a) { k += N-1; dat.set(k,dat.get(k)+a); while(k>0){ k = (k-1)/2; dat.set(k,dat.get(k*2+1)+dat.get(k*2+2)); } } int query(int a,int b, int k, int l ,int r) { if(r<=a||b<=l) return d1; if(a<=l&&r<=b) return dat.get(k); int vl = query(a,b,k*2+1,l,(l+r)/2); int vr = query(a,b,k*2+2,(l+r)/2,r); return vl+vr; } int query(int a,int b){ return query(a,b,0,0,N); } } class AddSumLazySegmentTree { int N; long[] dat; long[] laz; AddSumLazySegmentTree(long[] v){ init(v.length); for(int i=0;i=0;i--) { dat[i]=dat[i*2+1]+dat[i*2+2]; } } void init(int n) { N = 1; while(N0) { s += val[i]; i -= i & (-i); } return s; } void add(int i,int x) { if(i==0)return; while(it) { return i; }else { return find(t,root[i]); } } public void unite(int x,int y,int t) { now = t; x = find(t,x); y = find(t,y); if(x==y)return; if(rank[x]1) { int mid = (ok+ng)/2; if(find(mid,x)==find(mid,y)) { ok = mid; }else { ng = mid; } } return ok; } } class Graph { ArrayList[] list; int size; TreeSet Edges = new TreeSet(new LinkEdgeComparator()); @SuppressWarnings("unchecked") Graph(int N){ size = N; list = new ArrayList[N]; for(int i=0;i(); } } public long[] dicount(int s) { long[] L = new long[size]; long[] c = new long[size]; int mod = 1000000007; for(int i=0;i Q = new PriorityQueue(new LongIntComparator()); Q.add(new LongIntPair(0,s)); while(!Q.isEmpty()){ LongIntPair C = Q.poll(); if(v[C.b]==0){ L[C.b] = C.a; v[C.b] = 1; for(Edge D:list[C.b]) { //System.out.println(C.b +" "+ D.to); if(L[D.to]==-1||L[D.to]>L[C.b]+D.cost) { L[D.to]=L[C.b]+D.cost; c[D.to] = c[C.b]; Q.add(new LongIntPair(L[C.b]+D.cost,D.to)); }else if(L[D.to]==L[C.b]+D.cost) { c[D.to] += c[C.b]; } c[D.to] %= mod; } } } return c; } public long[] roots(int s) { int[] in = new int[size]; ArrayDeque q = new ArrayDeque(); long[] N = new long[size]; long mod = 1000000007; for(int i=0;i=mod)N[e.to]-= mod; in[e.to]--; if(in[e.to]==0)q.add(e.to); } } return N; } void addEdge(int a,int b){ list[a].add(new Edge(b,1)); } void addWeightedEdge(int a,int b,long c){ list[a].add(new Edge(b,c)); } void addEgdes(int[] a,int[] b){ for(int i=0;i Q = new ArrayDeque(); Q.add(s); while(!Q.isEmpty()){ int v = Q.poll(); for(Edge e:list[v]){ int w = e.to; long c = e.cost; if(L[w]==-1){ L[w] = L[v] + c; Q.add(w); } } } return L; } long[][] bfswithrev(int s){ long[][] L = new long[2][size]; for(int i=0;i Q = new ArrayDeque(); Q.add(s); while(!Q.isEmpty()){ int v = Q.poll(); for(Edge e:list[v]){ int w = e.to; long c = e.cost; if(L[0][w]==-1){ L[0][w] = L[0][v] + c; L[1][w] = v; Q.add(w); } } } return L; } long[] bfs2(int[] d,int s){ long[] L = new long[size]; for(int i=0;i Q = new ArrayDeque(); Q.add(s); while(!Q.isEmpty()){ int v = Q.poll(); for(Edge e:list[v]){ int w = e.to; long c = e.cost; if(L[w]==-1){ d[w] = p; p++; L[w] = L[v] + c; Q.add(w); } } } return L; } boolean bfs3(int s,long[] L, int[] vi){ if(vi[s]==1) return true; vi[s] = 1; ArrayDeque Q = new ArrayDeque(); Q.add(s); while(!Q.isEmpty()){ int v = Q.poll(); for(Edge e:list[v]){ int w = e.to; long c = e.cost; if(vi[e.to]==0) { L[e.to] = (int)c - L[v]; Q.add(w); vi[e.to] = 1; }else { if(L[e.to]!=(int)c - L[v]) { return false; } } } } return true; } int[] isTwoColor(){ int[] L = new int[size]; for(int i=0;i Q = new ArrayDeque(); Q.add(0); while(!Q.isEmpty()){ int v = Q.poll(); for(Edge e:list[v]){ int w = e.to; if(L[w]==-1){ L[w] = 1-L[v]; Q.add(w); }else{ if(L[v]+L[w]!=1){ L[0] = -2; } } } } return L; } void isTwoColor2(int i,int[] L){ L[i] = 0; ArrayDeque Q = new ArrayDeque(); Q.add(i); while(!Q.isEmpty()){ int v = Q.poll(); for(Edge e:list[v]){ int w = e.to; if(L[w]==-1){ L[w] = 1-L[v]; Q.add(w); }else{ if(L[v]+L[w]!=1){ L[0] = -2; } } } } } long[] dijkstra(int s){ long[] L = new long[size]; for(int i=0;i Q = new PriorityQueue(new LongIntComparator()); Q.add(new LongIntPair(0,s)); while(!Q.isEmpty()){ LongIntPair C = Q.poll(); if(v[C.b]==0){ L[C.b] = C.a; v[C.b] = 1; for(Edge D:list[C.b]) { if(L[D.to]==-1||L[D.to]>L[C.b]+D.cost) { L[D.to]=L[C.b]+D.cost; Q.add(new LongIntPair(L[C.b]+D.cost,D.to)); } } } } return L; } public long[] dijkstra2(int s, long mid) { long[] L = new long[size]; for(int i=0;i Q = new PriorityQueue(new LongIntComparator()); Q.add(new LongIntPair(0,s)); int lg = 1000000007; while(!Q.isEmpty()){ LongIntPair C = Q.poll(); if(v[C.b]==0){ L[C.b] = C.a; v[C.b] = 1; for(Edge D:list[C.b]) { if((L[D.to]==-1||L[D.to]>L[C.b]+D.cost%lg)&&L[C.b]+D.cost/lg<=mid) { L[D.to]=L[C.b]+D.cost%lg; Q.add(new LongIntPair(L[C.b]+D.cost%lg,D.to)); } } } } return L; } ArrayList makeapart(){ ArrayList ans = new ArrayList(); boolean[] b = new boolean[size]; int[] num = new int[size]; for(int i=0;i l = new ArrayList(); ArrayDeque Q = new ArrayDeque(); Q.add(i); b[i] = true; while(!Q.isEmpty()){ int v = Q.poll(); num[v] = sz; sz++; l.add(v); for(Edge e:list[v]){ if(!b[e.to]){ Q.add(e.to); b[e.to] = true; } } } Graph H = new Graph(sz); for(int e:l){ for(Edge E:list[e]){ H.addWeightedEdge(num[e],num[E.to],E.cost); } } ans.add(H); } return ans; } long[] bellmanFord(int s) { long inf = 1000000000; inf *= inf; long[] d = new long[size]; boolean[] n = new boolean[size]; d[s] = 0; for(int i=1;id[j]+E.cost){ d[E.to]=d[j]+E.cost; } } } } for(int i=0;id[j]+e.cost) { d[e.to]=d[j]+e.cost; n[e.to] = true; } if(n[j])n[e.to] = true; } } } for(int i=0;i Q = new PriorityQueue(new SampleComparator()); Q.add(new Pair(l,s)); while(!Q.isEmpty()){ Pair C = Q.poll(); if(v[(int)C.b]==0){ L[(int)C.b] = C.a; v[(int) C.b] = 1; for(Edge D:list[(int) C.b])Q.add(new Pair(Math.max(L[(int)C.b],D.cost),D.to)); } } return L; } long[] mintra(int s){ long[] L = new long[size]; for(int i=0;i Q = new PriorityQueue(new SampleComparator().reversed()); Q.add(new Pair(s,s)); while(!Q.isEmpty()){ Pair C = Q.poll(); if(v[(int)C.b]==0){ L[(int)C.b] = C.a; v[(int) C.b] = 1; for(Edge D:list[(int) C.b])Q.add(new Pair(Math.min(L[(int)C.b],D.cost),D.to)); } } return L; } long Kruskal(){ long r = 0; for(int i=0;i=0&&e.b>=0) { if(!UF.same(e.a,e.b)){ r += e.L; UF.unite(e.a,e.b); } } } return r; } ArrayList Kahntsort(){ ArrayList ans = new ArrayList(); PriorityQueue q = new PriorityQueue(); int[] in = new int[size]; for(int i=0;i0)return new ArrayList(); } return ans; } public Stack findCycle() { Stack ans = new Stack(); boolean[] v = new boolean[size]; boolean[] f = new boolean[size]; for(int i=0;ians, boolean[] v,boolean[] f) { v[i] = true; ans.push(i); for(Edge e:list[i]) { if(f[e.to]) continue; if(v[e.to]&&!f[e.to]) { return true; } if(findCycle(e.to,ans,v,f))return true; } ans.pop(); f[i] = true; return false; } RootedTree dfsTree(int i) { int[] u = new int[size]; RootedTree r = new RootedTree(size); dfsTree(i,u,r); return r; } private void dfsTree(int i, int[] u, RootedTree r) { u[i] = 1; r.trans[r.node] = i; r.node++; for(Edge e:list[i]) { if(u[e.to]==0) { r.list[i].add(e); u[e.to] = 1; dfsTree(e.to,u,r); } } } } class Tree extends Graph{ int[] trans; public Tree(int N) { super(N); } long[] tyokkei(){ long[] a = bfs(0); int md = -1; long m = 0; for(int i=0;i{ public int compare(DoubleLinkEdge P, DoubleLinkEdge Q) { return Double.compare(P.D,Q.D); } } class LinkEdgeComparator implements Comparator{ public int compare(LinkEdge P, LinkEdge Q) { return Long.compare(P.L,Q.L); } } class Pair{ long a; long b; Pair(long p,long q){ this.a = p; this.b = q; } public boolean equals(Object o){ Pair O = (Pair) o; return O.a==this.a&&O.b==this.b; } public int hashCode(){ return Objects.hash(a,b); } } class SampleComparator implements Comparator{ public int compare(Pair P, Pair Q) { long t = P.a-Q.a; if(t==0){ if(P.b==Q.b)return 0; return P.b>Q.b?1:-1; } return t>=0?1:-1; } } class LongIntPair{ long a; int b; LongIntPair(long p,int q){ this.a = p; this.b = q; } public boolean equals(Object o){ LongIntPair O = (LongIntPair) o; return O.a==this.a&&O.b==this.b; } public int hashCode(){ return Objects.hash(a,b); } } class LongIntComparator implements Comparator{ public int compare(LongIntPair P, LongIntPair Q) { long t = P.a-Q.a; if(t==0){ if(P.b>Q.b){ return 1; }else{ return -1; } } return t>=0?1:-1; } } class IntIntPair{ int a; int b; IntIntPair(int p,int q){ this.a = p; this.b = q; } IntIntPair(int p,int q,String s){ if(s.equals("sort")) { this.a = Math.min(p,q); this.b = Math.max(p,q); } } public boolean equals(Object o){ IntIntPair O = (IntIntPair) o; return O.a==this.a&&O.b==this.b; } public int hashCode(){ return Objects.hash(a,b); } } class IntIntComparator implements Comparator{ public int compare(IntIntPair P, IntIntPair Q) { int t = P.a-Q.a; if(t==0){ return P.b-Q.b; } return t; } } class CIPair{ char c; int i; CIPair(char C,int I){ c = C; i = I; } public boolean equals(Object o){ CIPair O = (CIPair) o; return O.c==this.c&&O.i==this.i; } public int hashCode(){ return Objects.hash(c,i); } } class DoublePair{ double a; double b; DoublePair(double p,double q){ this.a = p; this.b = q; } public boolean equals(Object o){ DoublePair O = (DoublePair) o; return O.a==this.a&&O.b==this.b; } public int hashCode(){ return Objects.hash(a,b); } } class Triplet{ long a; long b; long c; Triplet(long p,long q,long r){ a = p; b = q; c = r; } public boolean equals(Object o){ Triplet O = (Triplet) o; return O.a==this.a&&O.b==this.b&&O.c==this.c?true:false; } public int hashCode(){ return Objects.hash(a,b,c); } } class TripletComparator implements Comparator{ public int compare(Triplet P, Triplet Q) { long t = P.a-Q.a; if(t==0){ long tt = P.b-Q.b; if(tt==0) { if(P.c>Q.c) { return 1; }else if(P.c0?1:-1; } return t>=0?1:-1; } } class DDComparator implements Comparator{ public int compare(DoublePair P, DoublePair Q) { return P.a-Q.a>=0?1:-1; } } class DoubleTriplet{ double a; double b; double c; DoubleTriplet(double p,double q,double r){ this.a = p; this.b = q; this.c = r; } public boolean equals(Object o){ DoubleTriplet O = (DoubleTriplet) o; return O.a==this.a&&O.b==this.b&&O.c==this.c; } public int hashCode(){ return Objects.hash(a,b,c); } } class DoubleTripletComparator implements Comparator{ public int compare(DoubleTriplet P, DoubleTriplet Q) { if(P.a==Q.a) return 0; return P.a-Q.a>0?1:-1; } } class FastScanner { private final java.io.InputStream in = System.in; private final byte[] b = new byte[1024]; private int p = 0; private int bl = 0; private boolean hNB() { if (p0;j=(j-1)&i) { if(val[j]==1)dp[i]=Math.min(dp[i],dp[i^j]+1); } } return dp[(1<>1); } public void hakidashi(long[] A) { Arrays.sort(A); int N = A.length; int[] index = new int[61]; for(int i=0;i<=60;i++){ index[i] = -1; } int searching = 60; int [] used = new int[N]; while(searching>=0){ boolean b = true; for(int i=N-1;i>=0;i--){ for(int j=60;j>searching;j--){ if((A[i]>>j&1)==1){ if(i!=index[j]&&index[j]!=-1){ A[i] ^= A[index[j]]; //System.out.println(i+" changed by " + index[j]); //System.out.println(A[i]); } } } if((A[i]>>searching&1)==1&&used[i]==0){ //System.out.println("find " + searching+" is "+i); index[searching] = i; searching--; used[i] = 1; b = false; if(searching==-1){ searching = 0; } } } if(b){ searching--; } } for(int i=N-1;i>=0;i--){ for(int j=60;j>=searching;j--){ if((A[i]>>j&1)==1){ if(i!=index[j]&&index[j]!=-1){ A[i] ^= A[index[j]]; } } } } Arrays.sort(A); } public void printjudge(boolean b, String y, String n) { System.out.println(b?y:n); } public void printYN(boolean b) { printjudge(b,"Yes","No"); } public void printyn(boolean b) { printjudge(b,"yes","no"); } public void reverse(int[] x) { int[] r = new int[x.length]; for(int i=0;i=0&&td<=0)||(tc<=0&&td>=0))&&((ta>=0&&tb<=0)||(ta<=0&&tb>=0)); } public boolean dcross(double ax, double ay, double bx, double by, double cx, double cy, double dx, double dy) { double ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax); double tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx); double tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx); double td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx); return((tc>=0&&td<=0)||(tc<=0&&td>=0))&&((ta>=0&&tb<=0)||(ta<=0&&tb>=0)); } void buildFac(){ fac = new long[10000003]; revfac = new long[10000003]; fac[0] = 1; for(int i=1;i<=10000002;i++){ fac[i] = (fac[i-1] * i)%mod; } revfac[10000002] = rev(fac[10000002])%mod; for(int i=10000001;i>=0;i--) { revfac[i] = (revfac[i+1] * (i+1))%mod; } isBuild = true; } void buildFacn(int n){ fac = new long[n+1]; revfac = new long[n+1]; fac[0] = 1; for(int i=1;i<=n;i++){ fac[i] = (fac[i-1] * i)%mod; } revfac[n] = rev(fac[n])%mod; for(int i=n-1;i>=0;i--) { revfac[i] = (revfac[i+1] * (i+1))%mod; } isBuild = true; } public long[] buildrui(int[] a) { int n = a.length; long[] ans = new long[n]; ans[0] = a[0]; for(int i=1;i=r.length||d>=r[0].length) return mod; return r[c][d] - r[a-1][d] - r[c][b-1] + r[a-1][b-1]; } long divroundup(long n,long d) { if(n==0)return 0; return (n-1)/d+1; } public long sigma(long i) { return i*(i+1)/2; } public int digit(long i) { int ans = 1; while(i>=10) { i /= 10; ans++; } return ans; } public int digitsum(long n) { int ans = 0; while(n>0) { ans += n%10; n /= 10; } return ans; } public int popcount(int i) { int ans = 0; while(i>0) { ans += i%2; i /= 2; } return ans; } public boolean contains(int S,int i) {return (S>>i&1)==1;} public int bitremove(int S,int i) {return S&(~(1<>i&1)==1;} public long bitremove(long S,int i) {return S&(~(1<1) { int mid = (ok+ng)/2; if(d[mid]>i) { ok = mid; }else { ng = mid; } } return ok; } public int isSmaller(int[] d, int i) { int ok = -1; int ng = d.length; while(Math.abs(ok-ng)>1) { int mid = (ok+ng)/2; if(d[mid]1) { int mid = (ok+ng)/2; if(d[mid]>i) { ok = mid; }else { ng = mid; } } return ok; } public int isSmaller(long[] d, long i) { int ok = -1; int ng = d.length; while(Math.abs(ok-ng)>1) { int mid = (ok+ng)/2; if(d[mid] d, long i) { int ok = d.size(); int ng = -1; while(Math.abs(ok-ng)>1) { int mid = (ok+ng)/2; if(d.get(mid)>i) { ok = mid; }else { ng = mid; } } return ok; } public int isSmaller(ArrayList d, long i) { int ok = -1; int ng = d.size(); while(Math.abs(ok-ng)>1) { int mid = (ok+ng)/2; if(d.get(mid) primetable(int m) { HashSet pt = new HashSet(); for(int i=2;i<=m;i++) { boolean b = true; for(int d:pt) { if(i%d==0) { b = false; break; } } if(b) { pt.add(i); } } return pt; } public ArrayList primetablearray(int m) { ArrayList al = new ArrayList(); Queue q = new ArrayDeque(); for(int i=2;i<=m;i++) { q.add(i); } boolean[] b = new boolean[m+1]; while(!q.isEmpty()) { int e = q.poll(); if(!b[e]) { al.add(e); for(int j=1;e*j<=1000000;j++) { b[e*j] = true; } } } return al; } public boolean isprime(int e) { if(e==1) return false; for(int i=2;i*i<=e;i++) { if(e%i==0) return false; } return true; } public MultiSet Factrization(int e) { MultiSet ret = new MultiSet(); for(int i=2;i*i<=e;i++) { while(e%i==0) { ret.add(i); e /= i; } } if(e!=1)ret.add(e); return ret; } public HashMap hipPush(ArrayList l){ HashMap r = new HashMap(); TreeSet s = new TreeSet(); for(int e:l)s.add(e); int p = 0; for(int e:s) { r.put(e,p); p++; } return r; } public TreeMap thipPush(ArrayList l){ TreeMap r = new TreeMap(); Collections.sort(l); int b = -(1000000007+9393); int p = 0; for(int e:l) { if(b!=e) { r.put(e,p); p++; } b=e; } return r; } int[] count(int[] a) { int[] c = new int[max(a)+1]; for(int i=0;ia[i]){ m =a[i]; mindex = i; } } return m; } int min(int[] a){ int m = Integer.MAX_VALUE; for(int i=0;ia[i]){ m =a[i]; mindex = i; } } return m; } long sum(long[] a){ long s = 0; for(int i=0;i l) { long s = 0; for(int e:l)s += e; return s; } long gcd(long a, long b){ a = Math.abs(a); b = Math.abs(b); if(a==0)return b; if(b==0)return a; if(a%b==0) return b; else return gcd(b,a%b); } int igcd(int a, int b) { if(a%b==0) return b; else return igcd(b,a%b); } long lcm(long a, long b) {return a / gcd(a,b) * b;} public long perm(int a,int num) { if(!isBuild)buildFac(); return fac[a]*(rev(fac[a-num]))%mod; } void buildComb(int N) { comb = new long[N+1][N+1]; comb[0][0] = 1; for(int i=1;i<=N;i++) { comb[i][0] = 1; for(int j=1;jmod)comb[i][j]-=mod; } comb[i][i] = 1; } } public long comb(int a,int num){ if(a-num<0)return 0; if(num<0)return 0; if(!isBuild)buildFac(); return fac[a] * ((revfac[num]*revfac[a-num])%mod)%mod; } long mulchoose(int n,int k) { if(k==0) return 1; return comb(n+k-1,k); } long rev(long l) {return pow(l,mod-2);} void buildpow(int l,int i) { pow = new long[i+1]; pow[0] = 1; for(int j=1;j<=i;j++) { pow[j] = pow[j-1]*l; if(pow[j]>mod)pow[j] %= mod; } } void buildrevpow(int l,int i) { revpow = new long[i+1]; revpow[0] = 1; for(int j=1;j<=i;j++) { revpow[j] = revpow[j-1]*l; if(revpow[j]>mod) revpow[j] %= mod; } } long pow(long l, long i) { if(i==0)return 1; else{ if(i%2==0){ long val = pow(l,i/2); return val * val % mod; } else return pow(l,i-1) * l % mod; } } long mon(int i) { long ans = 0; for(int k=2;k<=i;k++) { ans += (k%2==0?1:-1) * revfac[k]; ans += mod; } ans %= mod; ans *= fac[i]; return ans%mod; } long dictnum(int[] A) { int N = A.length; long ans = 0; BinaryIndexedTree bit = new BinaryIndexedTree(N+1); buildFacn(N); for(int i=1;i<=N;i++) { bit.add(i,1); } for(int i=1;i<=N;i++) { int a = A[i-1]; ans += bit.sum(a-1) * fac[N-i] % mod; bit.add(a,-1); } return (ans+1)%mod; } }