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]);
}
}
