Contest Duration: - (local time) (100 minutes) Back to Home
E - Karuta /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• x, y の長さはいずれも n 以上
• 1 以上 n 以下の全ての整数 i に対し、xi 文字目と yi 文字目が等しい

• \displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j)

### 制約

• 2 \leq N \leq 5 \times 10^5
• N は整数
• S_i は英小文字からなる長さ 1 以上の文字列 (i = 1, 2, \dots, N)
• S_i の長さの総和は 5 \times 10^5 以下

### 入力

N
S_1
S_2
\vdots
S_N


### 出力

N 行出力せよ。i \, (i = 1, 2, \dots, N) 行目には、\displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j) を出力せよ。

### 入力例 1

3
abc
abb
aac


### 出力例 1

2
2
1


\mathrm{LCP}(S_1, S_2) = 2, \mathrm{LCP}(S_1, S_3) = 1, \mathrm{LCP}(S_2, S_3) = 1 です。

### 入力例 2

11
dabra
abra
bra
ra
a


### 出力例 2

4
3
2
1
0
1
0
4
3
2
1


Score : 500 points

### Problem Statement

You are given N strings consisting of lowercase English letters. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

For two strings x and y, \mathrm{LCP}(x, y) is defined to be the maximum integer n that satisfies all of the following conditions:

• The lengths of x and y are both at least n.
• For all integers i between 1 and n, inclusive, the i-th character of x and that of y are equal.

Find the following value for all i = 1, 2, \dots, N:

• \displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j)

### Constraints

• 2 \leq N \leq 5 \times 10^5
• N is an integer.
• S_i is a string of length at least 1 consisting of lowercase English letters (i = 1, 2, \dots, N).
• The sum of lengths of S_i is at most 5 \times 10^5.

### Input

The input is given from Standard Input in the following format:

N
S_1
S_2
\vdots
S_N


### Output

Print N lines. The i-th (i = 1, 2, \dots, N) line should contain \displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j).

### Sample Input 1

3
abc
abb
aac


### Sample Output 1

2
2
1


\mathrm{LCP}(S_1, S_2) = 2, \mathrm{LCP}(S_1, S_3) = 1, and \mathrm{LCP}(S_2, S_3) = 1.

### Sample Input 2

11
dabra
abra
bra
ra
a


### Sample Output 2

4
3
2
1
0
1
0
4
3
2
1