Background

Previously: The little square and the Lord of Darkness fought a great battle. In the end, the little square defeated the Lord of Darkness and successfully took the last triangle from him.

The triangle was spinning and purifying. Just as the purification was about to finish, the Lord of Darkness suddenly arrived, interrupted the triangle’s purification, and absorbed the triangle’s energy.

However, because the triangle’s energy was too huge, the Lord of Darkness mutated. The current Lord of Darkness keeps duplicating again and again, and eventually became a centipede...

Now, can the little square still stop the Lord of Darkness from destroying the world?

Problem Description

The centipede of the Lord of Darkness can destroy almost everything, so the little square is trapped in a hard fight...

Now the little square needs to weaken the attacks of the Lord of Darkness.

One attack of the Lord of Darkness can be represented by a string consisting only of lowercase letters.

Now the Lord of Darkness launches several attacks at the little square. For any two attacks, the little square can find their longest common substring and erase that part.

Now the little square wants to know: for any two attacks of the Lord of Darkness, what is the length of their longest common substring? Can you help?

Input Format

The first line contains an integer $n$, representing the number of strings.

The next $n$ lines each contain one string. It is guaranteed that the total length of all strings does not exceed $10^6$.

Output Format

Output a total of $n$ lines, each containing $n - 1$ positive integers.

The first positive integer in the first line represents the longest common substring of the $1$st string and the $2$nd string.

The second positive integer represents the longest common substring of the $1$st string and the $3$rd string.

...

The first positive integer in the second line represents the longest common substring of the $2$nd string and the $1$st string.

And so on.

3
abb
bcc
aba

1 2
1 1
2 1

Hint

For $30\%$ of the testdata, $n \le 5$, and the length of each string does not exceed $500$.

For $100\%$ of the testdata, $2 \le n \le 50$, and the total length of all strings does not exceed $10^6$.

Note: the memory limit of this problem is only $64$ MB. Please use a method with good memory usage.

In addition, for the test points worth $60$ pts, you will get $10$ pts for each point you pass.

For the remaining test points, you will get $40$ pts only if you pass all of them.

For all test points, the data is not guaranteed to be randomly generated.

Translated by ChatGPT 5