#include #include #include #include #include #include #include #define maxn 100007 #define grantN 1000007 #define modp 1000000007 #define mmmp 9973 #define eps (5E-1) #define minf2 (1E-10) #define lim1 30 #define lim2 300 using namespace std; typedef long long LL; const double PI=4*atan(1); const double PI2=PI*2; int n,m,tot; LL gg,jj; typedef struct sege { int st,cnt; int nxt[27]; //struct sege *nxt[27]; friend int operator<(struct sege x, struct sege y) { return x.st>=1; } return res; } void extgcd(int a, int b, int &x, int &y) { if (b != 0) { extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } } int mod_inv(int a, int p) { int x, y; extgcd(a, p, x, y); return (p + x % p) % p; } int invm(int x, int p) { x%=p; if (x==0) return 0; else return mod_inv(x,p); } int crt(int x, int m1, int y, int m2) { if (y>x) return ((y-x)%m2*invm(m1,m2)%m2*m1%m2+x)%m2; else return ((x-y)%m1*invm(m2,m1)%m1*m2%m1+y)%m1; } E e[grantN]; char s[40],t[40]; void ins(int en, char * s) { if ((*s)=='\0') { e[en].st=1; ++e[en].cnt; return; } int k=*s-'a'; if (e[en].nxt[k]==-1) { e[en].nxt[k]=++tot; for (int i=0;i<26;++i) e[tot].nxt[i]=-1; e[tot].st=0; e[tot].cnt=0; } ++e[en].cnt; ins(e[en].nxt[k],s+1); } int del(int en, char * s) { int k=*s-'a'; if (*(s+1)=='\0') { int tmp; e[en].cnt-=(tmp=e[e[en].nxt[k]].cnt); e[en].nxt[k]=-1; return tmp; } int tmp=0; if (e[en].nxt[k]!=-1) { e[en].cnt-=(tmp=del(e[en].nxt[k],s+1)); } return tmp; } int mfind(int en, char * s) { if ((*s)=='\0') { return e[en].cnt; } int k=*s-'a'; if (e[en].nxt[k]!=-1) { return mfind(e[en].nxt[k],s+1); } else return 0; } int main() { int T; LL N; //scanf("%d",&T); //T=1; srand(time(0)); while (scanf("%d",&n)!=EOF) //printf("%d\n",strcmp("aaa","aaa")); //while (T--) //for (int ci=1;ci<=T;++ci) { for (int i=0;i<26;++i) e[0].nxt[i]=-1; tot=0; for (int i=0;i