题目描述

给定 $N$ 个由小写英文字母组成的字符串，设第 $i$ 个字符串为 $S_i$ ($i = 1, 2, \\ldots, N$)。

对于两个字符串 $x$ 和 $y$，我们定义 $\\mathrm{LCP}(x, y)$ 为满足以下条件的最大整数 $n$：

• $x$ 和 $y$ 的长度都至少为 $n$。
• 对于 $1$ 到 $n$ 之间的所有整数 $i$，$x$ 和 $y$ 的第 $i$ 个字符相等。

对于所有 $i = 1, 2, \\ldots, N$，求以下值：

• $\\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, \\ldots, N$)。
• $S_i$ 的长度之和不超过 $5 \\times 10^5$。

输入

输入以以下格式从标准输入给出：

$N$ $S_1$ $S_2$ $\\vdots$ $S_N$

输出

输出 $N$ 行。第 $i$ 行应包含 $\\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
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
a

示例输出 2

4
3
2
1
0
1
0
4
3
2
1