Description

黑暗之主的蜈蚣几乎可以毁灭一切，因此小正方形陷入了苦战……

小正方形现在需要减弱黑暗之主的攻击。

一个黑暗之主的攻击可以用一个仅有小写字母的字符串表示。

现在黑暗之主向小正方形发动了若干攻击，对于两个攻击，小正方形能选出它们最长的公共子串，并把这一段消除。

现在小正方形想要知道，对于任意两个黑暗之主的攻击，它们的最长公共子串长度是多少，你能帮帮它吗？

Input Format

第一行为一个整数 $n$，表示字符串数目。

接下来 $n$ 行，一行一个字符串，保证所有字符串长度之和不超过 $10^6$。

Output Format

输出共有 $n$ 行，每行 $n - 1$个正整数。

第一行第一个正整数表示第 $1$ 个串与第 $2$ 个串的最长公共子串。

第二个正整数表示第 $1$ 个串与第 $3$ 个串的最长公共子串。

……

第二行第一个正整数表示第 $2$ 个串与第 $1$ 个串的最长公共子串。

以此类推。

3
abb
bcc
aba

1 2
1 1
2 1

Hint

对于 $30\%$ 的数据，$n \le 5$，每个字符串长度不超过 $500$。

对于 $100\%$ 的数据，$2 \le n \le 50$，字符串长度之和不超过 $10^6$。

注意：本题内存限制仅为 $64$ MB,请尽量使用内存运用优秀的方法。

另外，对于占 $60$ pts 的测试点，您每通过一个点即可获得 $10$ pts。

对于剩下的测试点，您只有全部通过才能获得 $40$ pts。

对于所有数据点，不保证数据为随机生成。