前不久，lcs 终于决定看一下后缀数组了，那么什么是后缀数组呢？
首先明确一些定义：
字符集：一个字符集Σ是一个建立了全序关系的集合，也就是说，Σ中的任意两个不同的元素α和β都可以比较大小，要么α < β，要么β < α（也就是α > β）。字符集Σ中的元素称为字符。
字符串：一个字符串S是将n个字符顺次排列形成的数组，n称为S的长度，表示为len(S)。S的第i个字符表示为S[i]。
子串：字符串S的子串S[i..j]，i≤j，表示S串中从i到j这一段，也就是顺次排列S[i],S[i+1],...,S[j]形成的字符串。
后缀：后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串S的从i开头的后缀表示为Suffix(S,i)，也就是Suffix(S,i) = S[i..len(S)]。
关于字符串的大小比较，是指通常所说的“字典顺序”比较，也就是对于两个字符串u、v，令i从1开始顺次比较u[i]和v[i]，如果相等则令i加1，否则若u[i] < v[i]则认为u < v，u[i] > v[i]则认为u > v（也就是v < u），比较结束。如果i > len(u)或者i > len(v)仍比较不出结果，那么若len(u) < len(v)则认为u < v，若len(u) = len(v)则认为u = v，若len(u) > len(v)则u > v。
从字符串的大小比较的定义来看，S的两个开头位置不同的后缀u和v进行比较的结果不可能是相等，因为u = v的必要条件len(u) = len(v)在这里不可能满足。
下面我们约定一个字符集Σ和一个字符串S，设len(S) = n，且S[n] = '$'，（在 C/C++ 中，一般是 ‘\0’ ），也就是说S以一个特殊字符'$'结尾，并且'$'小于Σ中的任何一个字符。除了S[n]之外，S中的其他字符都属于Σ。对于约定的字符串S，从位置i开头的后缀直接写成Suffix(i)，省去参数S。
后缀数组 后缀数组SA是一个一维数组，它保存1..n的某个排列SA[1],SA[2],...SA[n]，并且保证 Suffix(SA[i]) < Suffix(SA[i+1]),1 ≤ i < n。也就是将S的n个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA中。
那么，现在你知道什么是后缀数组了吗？你的任务就是，对于给定的字符串，输出其后缀数组和对应后缀。
对于每组数据，顺序输出后缀数组的每一项，以及对应后缀，并用一个空格隔开（参考样例输出）。相邻两组数据之间用一个空行隔开。
9 a
8 aa
7 aaa
6 aaaa
5 aaaaa
4 aaaaaa
3 aaaaaaa
2 aaaaaaaa
1 aaaaaaaaa
9 a
7 aba
5 ababa
3 abababa
1 ababababa
8 ba
6 baba
4 bababa
2 babababa
