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.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 int mod = 1000000007; static long inf = (long)1e17; static int[] dx = {0,1,0,-1}; static int[] dy = {1,0,-1,0}; public static void main(String[] args) { int N = sc.nextInt(); ArrayList l = new ArrayList(); ArrayList m = new ArrayList(); for(int i=0;i map = mp.hipPush(m); Collections.sort(l,new CubeComparator()); N *= 3; int[][] dp = new int[N+1][(1<{ public int compare(Cube P, Cube Q) { return P.X==Q.X?P.N-Q.N:P.X-Q.X; } } class GridGraph extends Graph{ int N; int M; String[] S; HashMap map; GridGraph(int n,int m,String[] s,char[] c){ super(n*m); N = n; M = m; S = s; map = new HashMap(); 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 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)&&S[nx][ny]!=b) { int w = toint(nx,ny); if(L[w]==-1){ L[w] = L[v] + 1; Q.add(w); } } } } return L; } int[][] bfs2(char C,int K){ int s = map.get(C); int[][] L = new int[N*M][K+1]; for(int i=0;i Q = new ArrayDeque(); Q.add(new IntIntPair(s,0)); 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.a/M; int y = v.a%M; int h = v.b; int nx = x+dx[i]; int ny = y+dy[i]; if(X.isIn(nx)&&Y.isIn(ny)&&S[nx][ny]!=b) { int ni = toint(nx,ny); int nh = S[nx][ny]==w?h+1:h; if(nh>K) continue; if(L[ni][nh]==1000000007){ L[ni][nh] = L[v.a][h] + 1; Q.add(new IntIntPair(ni,nh)); } } } } 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 l; IntTrie(){ l = new ArrayList(); l.add(new IntTrieNode()); } void add(int[] a,int W){ int now = 0; for(int i=0;i l; MapTrie(){ l = new ArrayList(); l.add(new MapTrieNode()); } void add(int[] a,int W){ int now = 0; for(int i=0;i Exist = new HashMap(); int leave = -1; MapTrieNode(){ } } class Trie{ int nodenumber = 1; ArrayList 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{ int l; int r; int length; Range(int L,int R){ l = L; r = R; length = R-L+1; } boolean isIn(int x) { return (l<=x&&x<=r); } } class LeftComparator implements Comparator{ public int compare(Range P, Range Q) { return P.l-Q.l; } } class RightComparator implements Comparator{ public int compare(Range P, Range Q) { return P.r-Q.r; } } class LengthComparator implements Comparator{ public int compare(Range P, Range Q) { return 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 x,int i) { 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(); } } 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[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; } 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; } long[] dijkstra(int s){ long[] L = new long[size]; for(int i=0;i Q = new PriorityQueue(new LongIntSampleComparator()); 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; } 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; } 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; 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{ public Tree(int N) { super(N); } long[] tyokkei(){ long[][] a = bfs(0); System.out.println(); int md = -1; long m = 0; for(int i=0;i{ public int compare(LinkEdge P, LinkEdge Q) { long t = P.L-Q.L; if(t==0){ if(P.a>Q.a){ return 1; }else{ return P.b>Q.b?1:-1; } } return t>=0?1:-1; } } 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 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){ 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){ Pair O = (Pair) o; return O.a==this.a&&O.b==this.b; } public int hashCode(){ return Objects.hash(a,b); } } class LongIntSampleComparator 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; } 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 IntIntSampleComparator 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 DoublePair{ double a; double b; DoublePair(double p,double 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 DDSampleComparator implements Comparator{ public int compare(DoublePair P, DoublePair Q) { return P.b-Q.b>=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 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<=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=10) { i /= 10; ans++; } 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<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 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 = -(mod+9393); int p = 0; for(int e:l) { if(b!=e) { r.put(e,p); p++; } b=e; } return r; } long max(long[] a){ long M = 0; 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;imod)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; } }