问题描述

给定 $N$ 个由小写英文字母组成的字符串 $S_1, S_2, \ldots, S_N$。

对于两个字符串 $x, y$，定义 $\mathrm{LCP}(x, y)$ 为它们的最长公共前缀（Longest Common Prefix）的长度，即满足以下条件的最大整数 $n$：

• $x$ 和 $y$ 的长度均不小于 $n$；
• 对于所有 $1 \leq k \leq n$，$x$ 的第 $k$ 个字符与 $y$ 的第 $k$ 个字符相同。

对于每个 $i \in \{1, 2, \ldots, N\}$，请你求出：

$$\max_{1 \leq j \leq N, \, j \neq i} \mathrm{LCP}(S_i, S_j)$$

输入格式

第一行输入一个正整数 $N$，表示字符串的数量。

接下来输入 $N$ 行，第 $i$ 行包含一个由小写英文字母组成的字符串 $S_i$。

输出格式

输出共 $N$ 行，第 $i$ 行输出一个整数，表示 $\displaystyle\max_{j \neq i} \mathrm{LCP}(S_i, S_j)$。

样例输入 1

3
abc
abb
aac

样例输出 1

2
2
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

说明

样例 1 解释：

• $\mathrm{LCP}(S_1, S_2) = \mathrm{LCP}(\text{"abc"}, \text{"abb"}) = 2$；
• $\mathrm{LCP}(S_1, S_3) = \mathrm{LCP}(\text{"abc"}, \text{"aac"}) = 1$；
• $\mathrm{LCP}(S_2, S_3) = \mathrm{LCP}(\text{"abb"}, \text{"aac"}) = 1$。

因此：

• 对于 $S_1$，与其他串的最大 LCP 为 $\max(2, 1) = 2$；
• 对于 $S_2$，与其他串的最大 LCP 为 $\max(2, 1) = 2$；
• 对于 $S_3$，与其他串的最大 LCP 为 $\max(1, 1) = 1$。

评测数据规模

对于所有评测数据：

• $2 \leq N \leq 5 \times 10^5$
• $1 \leq |S_i| \quad (1 \leq i \leq N)$
• 所有字符串的长度之和满足 $\sum_{i=1}^N |S_i| \leq 5 \times 10^5$
• 字符串仅包含小写英文字母
• 所有输入均为整数或合法字符串