struct SAM {	
        string S;
	int t[nn][27], pre[nn], len[nn];
	int last, siz;
	vector<int> e[nn];
	void extend(int ch) {
		int np = ++siz;
		len[np] = len[last] + 1; e[len[np]].pb(np);
		int p = last; last = np;
		for (; !t[p][ch]; p = pre[p]) t[p][ch] = np;
		if (!p && t[p][ch] == np) pre[np] = 0;
		else
		{
			int q = t[p][ch];
			if (len[q] == len[p] + 1) pre[np] = q;
			else
			{
				int nq = ++siz; len[nq] = len[p] + 1; e[len[nq]].pb(nq);
				memcpy(t[nq], t[q], sizeof(t[q]));
				pre[nq] = pre[q];
				pre[q] = pre[np] = nq;
				for (; t[p][ch] == q; p = pre[p]) t[p][ch] = nq;
			}
		}
	}
	void dfs(int x, string s) {
		cout << s << endl;
		for (int i = 0; i < 26; ++i) if (t[x][i]) {
			dfs(t[x][i], s+(char)('a' + i));
		}
	}
	void build() {
		cin >> S;
		for (int i = 0; i < S.size(); ++i) extend(S[i] - 'a', kind);
	//	dfs(0, "");
	}
} suf; 
double dist(pp x,pp y){
	return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));
}
void calc(pp &ans,pp x,pp y){
	ans.x=(x.x+y.x)/2.0;
	ans.y=(x.y+y.y)/2.0;
	ans.r=dist(x,y)/2.0;
}
void work(){
	if (n==1) { puts("0.000");return; }
	pp ans; calc(ans,p[1],p[2]);
	rep(i,3,n)
	{
		if (dist(ans,p[i]) <= ans.r) continue;
		calc(ans,p[1],p[i]);
		rep(j,2,i-1)
		{
			if (dist(ans,p[j]) <= ans.r) continue;
			calc(ans,p[i],p[j]);
			rep(k,1,j-1)
			{
				if (dist(ans,p[k]) <= ans.r) continue;
                double a1=2*(p[j].x-p[i].x),b1=2*(p[j].y-p[i].y),c1=sqr(p[j].x)-sqr(p[i].x)+sqr(p[j].y)-sqr(p[i].y);
                double a2=2*(p[j].x-p[k].x),b2=2*(p[j].y-p[k].y),c2=sqr(p[j].x)-sqr(p[k].x)+sqr(p[j].y)-sqr(p[k].y);
                ans.x=(c1*b2-c2*b1)/(a1*b2-a2*b1);
                ans.y=(c1*a2-c2*a1)/(b1*a2-b2*a1);
                ans.r=dist(ans,p[i]);
			}
		}
	}
	printf("%.3f\n",ans.r);
}
namespace KM{
    const int N=110;
    int a[N][N],dx[N],dy[N],g[N],f[N],b[N],slack[N],n;
    bool hungary(int x){
        if (!x) return 1;
        f[x]=1;
        rep(i,1,n){
            if (g[i]) continue;
            int t=dx[x]+dy[i]-a[x][i];
            if (!t){
                g[i]=1;
                if (hungary(b[i])){
                    b[i]=x;
                    return 1;
                }
            } else slack[i]=min(slack[i],t);
        }
        return 0;
    }
    void solve(){
        clr(dy);
        rep(i,1,n){
            dx[i]=a[i][1];
            rep(j,1,n) dx[i]=max(dx[i],a[i][j]);
        }
        rep(i,1,n){
            memset(slack,0x7f,sizeof(slack));
            clr(f);clr(g);
            while (!hungary(i)){
                int d=INF;
                rep(j,1,n) if (!g[j]) d=min(d,slack[j]);
                rep(j,1,n){
                    if (f[j]) dx[j]-=d;
                    if (g[j]) dy[j]+=d;
                }
                clr(f);clr(g);
            }
        }
    }
    void init(int v){
        n=v;
        clr(a);clr(b);
    }
}
const int nnn=1000010;
char S[nnn];
PII w[nnn];
int ran[nnn],sa[nnn],height[nnn],node[nnn][2],g[nnn],other[nnn],next[nnn],f[nnn];
int es;

bool cmp(int x,int y) {return S[x]<S[y];}
void suffix(char *S,int L,int *rank,int *sa,int *height)
{
    rep(i,0,L+10) rank[i]=sa[i]=0;
      
    rep(i,1,L) sa[i]=i;
    sort(sa+1,sa+1+L,cmp);
    rank[sa[1]]=1;
    rep(i,2,L)
    {
        if (S[sa[i]] == S[sa[i-1]]) rank[sa[i]]=rank[sa[i-1]];
        else rank[sa[i]]=rank[sa[i-1]]+1;
    }
      
    for (int p=1;1;p<<=1)
    {
        for (int i=1;i<=L;++i)
        {
            node[i][0]=rank[i];
            node[i][1]=(i+p>L)?0:rank[i+p];
        }
          
        rep(i,0,L) g[i]=0;
        es=0;
        rep(i,1,L)
        {
            other[++es]=i;
            next[es]=g[node[i][1]];
            g[node[i][1]]=es;
        }
          
        int cnt=0;
        dep(i,L,0)
        {
            for (int p=g[i];p;p=next[p])
                sa[++cnt]=other[p];
        }
          
        rep(i,0,L) g[i]=0;
        es=0;
        rep(i,1,L)
        {
            other[++es]=sa[i];
            next[es]=g[node[sa[i]][0]];
            g[node[sa[i]][0]]=es;
        }
          
        cnt=0;
        rep(i,0,L)
        {
            for (int p=g[i];p;p=next[p])
                sa[++cnt]=other[p];
        }
          
        int f=0;
        rank[sa[1]]=1;
        rep(i,2,L)
            if (node[sa[i]][0]==node[sa[i-1]][0] && node[sa[i]][1]==node[sa[i-1]][1])
                rank[sa[i]] = rank[sa[i-1]];
            else
            {
                rank[sa[i]] = rank[sa[i-1]]+1;
                if (rank[sa[i]] == L) f=1;
            }
        if (f) break;
    }
      
    int H=0;
    rep(i,1,L)
    {
        if (rank[i]==0) { H=height[0]=0;continue; }
        if (H) H--;
        int j=sa[rank[i]-1];
        while (j+H<=L && i+H<=L && S[j+H]==S[i+H]) H++;
        height[rank[i]]=H;
    }
}

const int ne = 300010,inf=1<<30;
struct MAXFLOW
{
    int S,T,es,flow,n;
    int g[ne],other[ne],next[ne],va[ne],vh[ne],di[ne],dis[ne],his[ne],pre[ne],v[ne];
    void insert(int x, int y ,int z)
    {
        other[++es] = y; next[es] = g[x]; g[x] = es; va[es] = z;
        other[++es] = x; next[es] = g[y]; g[y] = es; va[es] = 0;
    }
    void init(int _S, int _T, int _n)
    {
        es = 1; flow = 0;
        S = _S; T = _T; n = _n;
        rep(i, 0, _n+10) g[i] = vh[i] = v[i] = dis[i] = 0;
    }
    void sap()
    {
        int aug = inf;
        rep(i,0,n) di[i] = g[i];
        vh[0] = n;
        int i = S;
        while (dis[S] < n)
        {
            his[i] = aug; int flag = 0;
            for (int p = di[i]; p; p = next[p])
            {
                int j = other[p];
                if (va[p] > 0 && dis[i] == dis[j] + 1)
                {
                    flag = 1; di[i] = p; pre[j] = p; aug = min(aug, va[p]); i = j;
                    if (i == T)
                    {
                        flow += aug;
                        while (i != S)
                        {
                            va[pre[i]] -= aug;
                            va[pre[i]^1] += aug;
                            i = other[pre[i] ^ 1];
                        } aug = inf; // !!!!!
 
                    } 
                    break;
                }
            }
            if (flag) continue;
            int min = n-1, j1;
            for (int p = g[i]; p; p = next[p])
                if (va[p] > 0 && dis[other[p]] < min) min = dis[other[p]], j1 = p;
            if (--vh[dis[i]] == 0) break;
            dis[i] = min+1;
            ++vh[dis[i]];
            di[i] = j1;
            if (i != S) { i = other[pre[i] ^ 1]; aug = his[i]; }
        }
    }
    void bfs(int s)
    {
        queue<int> Q; Q.push(s); v[s] = 1;
        while (Q.size())
        {
            int x = Q.front(); Q.pop();
            for (int p = g[x]; p; p = next[p])
            {
                int j = other[p];
                if (va[p] <= 0 || v[j]) continue;
                v[j] = 1; Q.push(j);
            }
        }
    }
} T;
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

#define INF (1<<30)
#define ll long long
#define sz(x) ((int) (x.size()))
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define d(x) cout << x << endl
#define REP(i,x) for (int i = 0; i < (int)(x); ++i)
#define rep(i,a,b) for (int i = (int) a; i <= (int) b; ++i)
#define dep(i,a,b) for (int i = (int) a; i >= (int) b; --i)
#define PII pair<int,int>

struct node {
	int key,weight;
	node *left,*right;
	node(int _key,int _weight,node*_left,node*_right):
		key(_key),weight(_weight),left(_left),right(_right){}
} *t;
node*newnode(int key) {
	return new node(key,rand(),NULL,NULL);
}
node*merge(node *a,node *b) {
	if (!a) return b;
	if (!b) return a;
	if (a->weight<b->weight)
		return new node(a->key,a->weight,a->left,merge(a->right,b));
	else
		return new node(b->key,b->weight,merge(a,b->left),b->right);
}
node*split_l(node*a,int key) {
	if (!a) return NULL;
	if (a->key<key)
		return new node(a->key,a->weight,a->left,split_l(a->right,key));
	else
		return split_l(a->left,key);
}
node*split_r(node*a,int key) {
	if (!a) return NULL;
	if (a->key>key)
		return new node(a->key,a->weight,split_r(a->left,key),a->right);
	else
		return split_r(a->right,key);
}
node*insert(node *a,int x) {
	return merge(merge(split_l(a,x),newnode(x)),split_r(a,x));
}
node*remove(node *a,int x) {
	return merge(split_l(a,x),split_r(a,x));
}
void dfs(node *a) {
	if (!a) return;
	dfs(a->left);printf("%d\n",a->key);dfs(a->right);
}
int a[100010];
const int nn=100000;
int main() {
	 freopen("1", "w", stdout);
	rep(i,1,nn) a[i]=i;
	random_shuffle(a+1,a+1+nn);
	rep(i,1,nn) t=insert(t,a[i]);
	dfs(t);
	return 0;
}
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

#define INF (1<<30)
#define ll long long
#define sz(x) ((int) (x.size()))
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define d(x) cout << x << endl
#define REP(i,x) for (int i = 0; i < (int)(x); ++i)
#define rep(i,a,b) for (int i = (int) a; i <= (int) b; ++i)
#define dep(i,a,b) for (int i = (int) a; i >= (int) b; --i)
#define foreach(it,x) for (typeof((x).begin()) it=(x).begin();it!=(x).end();++it)
#define PII pair<int,int>

struct point3
{
	double x,y,z;
	point3() {}
	point3(double _x,double _y,double _z) :
		x(_x),y(_y),z(_z) {}
};
struct face
{
	int a,b,c;
	bool del;
	face() {}
	face(int _a,int _b,int _c,bool _del) :
		a(_a),b(_b),c(_c),del(_del) {}
};
const int nn=1010;
const double eps=1e-10;
int N,t;
point3 p[nn];
face f[nn*nn];
int r[nn][nn];
point3 operator-(const point3 &x,const point3 &y)
{
	return point3(x.x-y.x,x.y-y.y,x.z-y.z);
}
point3 operator*(const point3 &x,const point3 &y)
{
	point3 z;
	z.x=x.y*y.z-x.z*y.y;
	z.y=x.z*y.x-x.x*y.z;
	z.z=x.x*y.y-x.y*y.x;
	return z;
}
double operator^(const point3 &x,const point3 &y)
{
	return x.x*y.x+x.y*y.y+x.z*y.z;
}
point3 det(face x)
{
	return (p[x.b]-p[x.a])*(p[x.c]-p[x.a]);
}
int sgn(double x)
{
	if (abs(x)<eps) return 0;
	return x<0 ? -1 : 1;
}
bool out(point3 a,face x)
{
	return sgn(det(x)^(a-p[x.a]))>0;
}
void work(int,int,int);
void dfs(int,int);
void dfs(int i,int x)
{
	f[x].del=1;
	work(i,f[x].a,f[x].b);
	work(i,f[x].b,f[x].c);
	work(i,f[x].c,f[x].a);
}
void work(int i,int a,int b)
{
	int x=r[b][a];
	if (f[x].del) return;
	if (out(p[i],f[x])) dfs(i,x);
	else
	{
		t++;
		f[t].a=a;f[t].b=b;f[t].c=i;
		r[a][b]=r[b][i]=r[i][a]=t;
	}
}
int M;
int v[nn];
int main()
{
	freopen("spring17.in", "r", stdin);
	scanf("%d%d",&N,&M);
	rep(i,1,N)
	{
		scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
		double tmp;
		scanf("%lf",&tmp);
	}
	random_shuffle(p+1,p+1+N);
	rep(i,1,4)
	{
		f[i]=face(i,i%4+1,(i+1)%4+1,0);
		if (out(p[(i+2)%4+1],f[i])) swap(f[i].a,f[i].b);
		r[f[i].a][f[i].b]=r[f[i].b][f[i].c]=r[f[i].c][f[i].a]=i;
	}
	t=4;
	rep(i,5,N)
	{
		rep(k,1,t)
		{
			if (!f[k].del&&out(p[i],f[k]))
			{
				dfs(i,k);
				break;
			}
		}
	}
	rep(i,1,t) if (!f[i].del) v[f[i].a]=v[f[i].b]=v[f[i].c]=1;
	int res=0;
	rep(i,1,N) res+=v[i];
	printf("%d\n",N-res);
	return 0;
}


#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

#define INF (1<<30)
#define ll long long
#define sz(x) ((int) (x.size()))
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define d(x) cout << x << endl
#define REP(i,x) for (int i = 0; i < (int)(x); ++i)
#define rep(i,a,b) for (int i = (int) a; i <= (int) b; ++i)
#define dep(i,a,b) for (int i = (int) a; i >= (int) b; --i)
#define foreach(it,x) for (typeof((x).begin()) it=(x).begin();it!=(x).end();++it)
#define PII pair<int,int>

ll mul(ll x,ll y,ll mod)
{
	return ((x*y-(ll)((long double)x*y/mod)*mod)%mod+mod)%mod;
}
ll power(ll x,ll y,ll mod)
{
	ll res=1;
	while (y)
	{
		if (y&1) res=mul(res,x,mod);
		x=mul(x,x,mod);y>>=1;
	}
	return res;
}
const int pr[]={2,3,5,7,11,13,17,19,23,29};
bool chk(ll x,ll p)
{
	if (x==1) return 0;
	if (x<=p) return 1;
	ll t=x-1,w=0;
	while (!(t&1)) w++,t>>=1;
	ll z=power(p,t,x);
	if (z==1||z==x-1) return 41;
	while (w--)
	{
		z=mul(z,z,x);
		if (w&&z==x-1) return 1;
	}
	return 0;
}
bool chk(ll x)
{
	rep(i,0,9) if (!chk(x,pr[i])) return 0;
	return 1;
}
ll a[100];
void rho(ll x)
{
	if (chk(x)) {a[++a[0]]=x;return;}
	if (x==4) {a[++a[0]]=2,a[++a[0]]=2;return;}
	if (x==1) return;
	while (1)
	{
		ll a=2,b=2,c=1,p=rand()%1000000000;
		while (c==1)
			a=(mul(a,a,x)+p)%x,
			b=(mul(b,b,x)+p)%x,
			b=(mul(b,b,x)+p)%x,
			c=__gcd(abs(a-b),x);
		if (c==x) continue;
		rho(c);rho(x/c);return;
	}
}
int main()
{
//	freopen("1.in", "r", stdin);
	ll n;cin>>n;rho(n);
	sort(a+1,a+1+a[0]);
	rep(i,1,a[0]) cout<<a[i]<<endl;
	return 0;
}


struct sgt {
	int t[nn][2],S[nn],RS[nn],del[nn],a[nn],q[nn],f[nn];
	int root,siz;
	void init() {
		root=0;
	}
	int newnode() {
		int x=++siz;
		t[x][0]=t[x][1]=del[x]=f[x]=a[x]=0;
		S[x]=RS[x]=1;
		return x;
	}
	bool bad(int x)	{
		return S[t[x][0]]>S[x]*A+5||S[t[x][1]]>S[x]*A+5;
	}
	void dfs(int x) {
		if (t[x][0]) dfs(t[x][0]);
		q[++q[0]]=x;
		if (t[x][1]) dfs(t[x][1]);
	}
	void update(int x) {
		S[x]=S[t[x][0]]+S[t[x][1]]+1;
		RS[x]=RS[t[x][0]]+RS[t[x][1]]+1-del[x];
	}
	void build(int &x,int l,int r,int fa) {
		int mid=l+r>>1;x=q[mid];f[x]=fa;
		t[x][0]=t[x][1]=0;
		if (l<mid) build(t[x][0],l,mid-1,x);
		if (mid<r) build(t[x][1],mid+1,r,x);
		update(x);
	}
	void rebuild(int x) {
		int y=f[x],c=t[y][1]==x;
		q[0]=0;
		dfs(x);
		if (!y) build(root,1,q[0],0);
		else build(t[y][c],1,q[0],y);
	}
	int insert(int &r,int x,int fa) {
		if (!r) {
			r=newnode();
			a[r]=x;f[r]=fa;
			return -1;
		}
		int res=-1;
		if (a[r]>x) res=insert(t[r][0],x,r);
		else res=insert(t[r][1],x,r);
		if (bad(r)) res=r;
		update(r);
		return res;
	}
	void delrebuild() {
		if (RS[root]<S[root]/2) rebuild(root);
	}
	void dele(int r,int d) {
		if (a[r]==d) del[r]=1;
		else if (a[r]>d) dele(t[r][0],d);
		else dele(t[r][1],d);
		update(r);
	}
	void Ins(int x) {
		int res=insert(root,x,0);
		if (res>0) rebuild(res);
	}
	void Del(int x) {
		dele(root,x);
		delrebuild();
	}
	void tour() {
		q[0]=0;dfs(root);
	}
} T;
namespace LCT {
	const int nn = 1000000;
	int t[nn][2], fa[nn], rev[nn], s[nn];
	int a[nn], w[nn], p[nn];
	bool isr(int x) {
		return !fa[x] || t[fa[x]][0] != x && t[fa[x]][1] != x;
	}
	void revit(int x) {
		if (!x) return;
		rev[x] ^= 1;
		swap(t[x][0], t[x][1]);
	}
	void push(int x) {
		if (!x) return;
		if (rev[x]) {
			revit(t[x][0]);
			revit(t[x][1]);
			rev[x] = 0;
		}
	}
	void update(int x) {
		s[x] = s[t[x][0]] + s[t[x][1]] + 1;
		w[x] = a[x]; p[x] = x;
		if (w[t[x][0]] > w[x]) w[x] = w[t[x][0]], p[x] = p[t[x][0]];
		if (w[t[x][1]] > w[x]) w[x] = w[t[x][1]], p[x] = p[t[x][1]];
	}
	void rotate(int x, int cx) {
		int y = fa[x], cy = t[fa[y]][1] == y;
		if (t[x][!cx]) fa[t[x][!cx]] = y; t[y][cx] = t[x][!cx];
		if (!isr(y)) t[fa[y]][cy] = x; fa[x] = fa[y];
		t[x][!cx] = y; fa[y] = x;
		update(y);
	}
	void splay(int x) {
		push(x);
		while (!isr(x)) {
			int y = fa[x], fy = fa[y];
			push(fy); push(y); push(x);
			int cx = t[y][1] == x, cy = t[fy][1] == y;
			if (isr(y)) {rotate(x, cx); break;}
			if (cx == cy) rotate(y, cy), rotate(x, cx);
			else rotate(x, cx), rotate(x, cy);
		}
		update(x);
	}
	void access(int x) {
		for (int v = 0; x; v = x, x = fa[x])
			splay(x), t[x][1] = v, update(x);
	}
	void resign(int x) {
		access(x); splay(x); revit(x);
	}
	int getroot(int x) {
		splay(x);
		while (1) {
			push(x);
			if (!t[x][0]) return x;
			x = t[x][0];
		}
	}
	bool link(int x, int y) {
		resign(x); access(y); splay(y);
		if (getroot(y) == x) return 0;
		fa[x] = y;
		return 1;
	}
	bool islink(int x, int y) {
		resign(x); access(y); splay(y);
		if (getroot(y) == x) return 1;
		return 0;
	}
	void cut(int x, int y) {
		resign(x);  access(y); splay(y);
		fa[x] = 0;
		t[y][0] = 0;
		update(y);
	}
	int query(int x, int y) {
		resign(x); access(y); splay(y);
		return p[y];
	}
}
struct fft
{
	cd w[20];
	int rev[ne],rr;
	void init()
	{
		w[19]=cd(cos(2*pi/(1<<19)),sin(2*pi/(1<<19)));
		dep(i,18,0) w[i]=w[i+1]*w[i+1];
	}
	void dft(cd *a,int rr,int inv)
	{
		rep(i,0,rr-1) rev[i]=(rev[i>>1]>>1)|((i&1)*(rr>>1));
		rep(i,0,rr-1) if (rev[i]<i) swap(a[i],a[rev[i]]);
		for (int i=0,ii=1;ii<rr;i++,ii<<=1)
		for (int j=0;j<rr;j+=ii<<1)
		{
			cd W=cd(1,0);
			rep(k,j,j+ii-1)
			{
				cd t=a[k+ii]*W;
				a[k+ii]=a[k]-t;
				a[k]=a[k]+t;
				W=W*w[i+1];
			}
		}
		if (inv)
		{
			rep(i,1,rr>>1) swap(a[i],a[rr-i]);
			rep(i,0,rr-1) a[i]=a[i]/(rr*1.);
		}
	}
	void mul(int n,cd *c,cd *a,cd *b)
	{
		rr=1;while (rr/2<n) rr<<=1;
		dft(a,rr,0);dft(b,rr,0);
		rep(i,0,rr-1) c[i]=a[i]*b[i];
		dft(c,rr,1);
	}
} D;
struct NTT {
	int rev[nn], rr, mod;
	ll w[22];
	void init() {
		mod = 998244353;
		w[19] = power(3, (mod-1)>>19, mod);
		dep(i, 18, 0) w[i] = w[i+1] * w[i+1] % mod;
	}
	void dft(int rr, ll *a, int invv) {
		rep(i,1,rr-1) rev[i] = (rev[i>>1] >> 1) | ((rr>>1) * (i & 1));
		rep(i,1,rr-1) if (i < rev[i]) swap(a[i], a[rev[i]]);
		for (int i = 0, ii = 1; ii < rr; i++, ii <<= 1)
		for (int j = 0; j < rr; j += ii << 1) {
			ll W = 1;
			rep(k,j,j+ii-1) {
				ll t = W * a[k+ii] % mod;
				a[k + ii] = (a[k] - t + mod) % mod;
				a[k] = (a[k] + t) % mod;
				W = W * w[i+1] % mod;
			}
		}
		if (invv) {
			rep(i,1,rr>>1) swap(a[i], a[rr-i]);
			ll inv = power(rr, mod-2, mod);
			rep(i,0,rr-1) a[i] = a[i] * inv % mod;
		}
	}
	void mul(int N, ll *c, ll *a, ll *b) {
		rr = 1;
		while (rr < N) rr <<= 1;
		dft(rr, a, 0); dft(rr, b, 0);
		rep(i,0,rr-1) c[i] = a[i] * b[i] % mod;
		dft(rr, c, 1);
	}
} D;
namespace CostFlow {
	const int nn = 110000;
	const int inf = 1e9;
	int other[nn], next[nn], g[nn], cost[nn], va[nn], d[nn], v[nn], ft[nn], fe[nn];
	int es, S, T, n, mincost;
	
	void insert(int x, int y, int z, int w) {
		other[++es] = y; next[es] = g[x]; g[x] = es; va[es] = z; cost[es] = w;
		other[++es] = x; next[es] = g[y]; g[y] = es; va[es] = 0; cost[es] = -w;
	}
	void init(int _S, int _T, int _n) {
		S = _S; T = _T; n = _n; es = 1; mincost = 0;
		for (int i = 0; i <= n; ++i) g[i] = 0;
		clr(g);clr(fe);clr(v);
	}
	bool spfa() {
		queue<int> Q;
		for (int i = 0; i <= n; ++i) d[i] = inf, v[i] = 0;
		d[S] = 0; v[S] = 1;
		Q.push(S);
		while (Q.size()) {
			int x = Q.front();
			Q.pop();
			v[x] = 0;
			for (int p = g[x]; p; p = next[p]) if (va[p] > 0) {
				int j = other[p];
				if (d[j] > d[x] + cost[p]) {
					d[j] = d[x] + cost[p];
					ft[j] = x;
					fe[j] = p;
					if (!v[j]) {
						v[j] = 1;
						Q.push(j);
					}
				}
			}
		}
		return d[T] < inf;
	}
	void augment() {
		int Min = inf;
		for (int i = T; i != S; i = other[fe[i] ^ 1]) Min = min(Min, va[fe[i]]);
		mincost += Min * d[T];
		for (int i = T; i != S; i = other[fe[i] ^ 1]) {
			va[fe[i]] -= Min;
			va[fe[i] ^ 1] += Min;
		}
	}
	int run() {
		while (spfa()) augment();
		return mincost;
	}
};
const int nn=501234;
char str[nn];
int n,t,K;
int rank[nn],sa[nn],height[nn],x[nn],y[nn],s[nn],a[nn];
 
void suffix()
{
    int M=0;
    rep(i,1,n) rank[i]=str[i],M=max(M,rank[i]);
    for (int j=1;;j<<=1)
    {
        rep(i,0,M) s[i]=0;
        rep(i,1,n) y[i]=(i+j<=n)?rank[i+j]:0,s[y[i]]++;
        rep(i,1,M) s[i]+=s[i-1];
        rep(i,1,n) sa[s[y[i]]--]=i;
        rep(i,0,M) s[i]=0;
        rep(i,1,n) s[rank[i]]++;
        rep(i,1,M) s[i]+=s[i-1];
        dep(i,n,1) x[s[rank[sa[i]]]--]=sa[i];
        rep(i,1,n) sa[i]=x[i],a[i]=rank[i];
        M=1;
        rank[sa[1]]=1;
        rep(i,2,n)
        {
            if (!(a[sa[i]]==a[sa[i-1]] && y[sa[i]]==y[sa[i-1]]))
                rank[sa[i]]=++M;
            else
                rank[sa[i]]=rank[sa[i-1]];
        }
        if (M==n) break;
    }
    int H=0;
    rep(i,1,n)
    {
        int x=sa[rank[i]-1];
        int y=i;
        if (H) H--;
        while (x+H<=n&&y+H<=n&&str[x+H]==str[y+H]) H++;
        height[rank[i]]=H;
    }
}
const double eps=1e-8;
double a[10010][1010];
int N,M;
int sgn(double x) {
    if (abs(x)<eps) return 0;
    return x>0?1:-1;
}
void pivot(int o,int e) {
    rep(i,0,N) if (i!=e) a[o][i]/=a[o][e];
    a[o][e]=1/a[o][e];
    rep(i,0,M) if (i!=o) {
        rep(j,0,N) if (j!=e) a[i][j]-=a[i][e]*a[o][j];
        a[i][e]*=-a[o][e];
    }
}
double simplex() {
    while (1) {
        double m=0;int p=-1,e=-1;
        rep(i,1,N) if (sgn(a[0][i]-m)>0) m=a[0][i],p=i;
        if (p<0) return -a[0][0];
        m=1e100;
        rep(i,1,M) if (sgn(a[i][p])>0&&sgn(m-a[i][0]/a[i][p])>0) m=a[i][0]/a[i][p],e=i;
        pivot(e,p);
    //  printf("%d\n",(int)-a[0][0]);
    }
}