Thẻ từ giống nhau nhất

Bối cảnh và bài toán

Một trò chơi ghép thẻ so sánh các từ từ trái sang phải. Với mỗi thẻ, người tổ chức muốn biết độ dài tiền tố chung dài nhất mà nó có thể chia sẻ với ít nhất một thẻ khác trong bộ.

Yêu cầu

Cho N chuỗi. Với mỗi S_i, in max_{j != i} LCP(S_i, S_j).

Input

Dòng đầu chứa N, sau đó là N dòng chứa các chuỗi S_i.

Output

In N dòng; dòng i là LCP lớn nhất của S_i với một chuỗi khác.

Ràng buộc

• 2 <= N <= 5 * 10^5
• Tổng độ dài các chuỗi không vượt 5 * 10^5.
• Chuỗi chỉ gồm chữ cái thường.

Chấm điểm

Ví dụ 1

Input

3
abc
abb
aac

Output

2
2
1

Giải thích. abc và abb có LCP bằng 2; aac chỉ chia sẻ ký tự đầu a.

Ví dụ 2

Input

4
a
ab
abc
z

Output

1
2
2
0

Giải thích. Mỗi từ trong nhánh a có thể chia sẻ prefix với từ khác; z không chia sẻ ký tự đầu với ai.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from: AtCoder Beginner Contest 287 – E – Karuta.