//后缀数组模板，MANX为数组的大小

 //支持的操作有计算后缀数组(sa数组)， 计算相邻两元素的最长公共前缀(height数组)，使用get_height();

 //计算两个后缀a, 和b的最长公共前缀，请先使用lcp_init(),再调用get_lcp(a, b)得到

 //下面的n是输入字符串的长度+1(n = strlen(s) + 1)， m是模板的范围 m=128表示在字母，数字范围内，可以扩大也可缩小

 //s[len] 是插入的一个比输入字符都要小的字符

 struct SufArray {

     char s[MAXN];

     int sa[MAXN], t[MAXN], t2[MAXN], c[MAXN], n, m;

     int rnk[MAXN], height[MAXN];//rnk和height数组

     int mi[MAXN][], idxK[MAXN];//用于计算LCP

     void init() {

         mem0(s);

         mem0(height);

     }

     //读入字符串作为输入

     void read_str() {

         gets(s);

         m = ;

         n = strlen(s);

         s[n++] = ' ';

     }

     void build_sa() {

         int *x = t, *y = t2;

         rep (i, , m - ) c[i] = ;

         rep (i, , n - ) c[x[i] = s[i]] ++;

         rep (i, , m - ) c[i] += c[i - ];

         dec (i, n - , ) sa[--c[x[i]]] = i;

         for(int k = ; k <= n; k <<= ) {

             int p = ;

             rep (i, n - k, n - ) y[p++] = i;

             rep (i, , n - ) if(sa[i] >= k) y[p++] = sa[i] - k;

             rep (i, , m - ) c[i] = ;

             rep (i, , n - ) c[x[y[i]]] ++;

             rep (i, , m - ) c[i] += c[i - ];

             dec (i, n - , ) sa[--c[x[y[i]]]] = y[i];

             swap(x, y);

             p = ;

             x[sa[]] = ;

             rep (i, , n - ) {

                 x[sa[i]] = y[sa[i - ]] == y[sa[i]] && y[sa[i - ] + k] == y[sa[i] + k] ? p -  : p++;

             }

             if(p >= n) break;

             m = p;

         }

     }

     void get_height() {

         int k = ;

         rep (i, , n - ) rnk[sa[i]] = i;

         rep (i, , n - ) {

             if(k) k --;

             int j = sa[rnk[i] - ];

             while(s[i + k] == s[j + k]) k ++;

             height[rnk[i]] = k;

         }

     }

     void rmq_init(int *a, int n) {

         rep (i, , n - ) mi[i][] = a[i];

         for(int j = ; ( << j) <= n; j ++) {

             for(int i = ; i + (<<j) -  < n; i ++) {

                 mi[i][j] = min(mi[i][j - ], mi[i + ( << (j - ))][j - ]);

             }

         }

         rep (len, , n) {

             idxK[len] = ;

             while(( << (idxK[len] + )) <= len) idxK[len] ++;

         }

     }

     int rmq_min(int l, int r) {

         int len = r - l + , k = idxK[len];

         return min(mi[l][k], mi[r - ( << k) + ][k]);

     }

     void lcp_init() {

         get_height();

         rmq_init(height, n);

     }

     int get_lcp(int a, int b) {

         if(a == b) return n - a - ;

         return rmq_min(min(rnk[a], rnk[b]) + , max(rnk[a], rnk[b]));

     }

     void solve() {

     }

 };