목록

최근 과학자들이 최초의 인류가 지구에 나타나기 전에 존재했던 모든 세계의 완전한 목록을 찾아냈다. 과학자들은 이 목록으로 여러 통계를 내려고 하며, 이를 위해 이름이 얼마나 비슷한지 정의한다.

두 이름의 길이 $x$인 접미사가 같고 길이 $x$인 접두사도 같으면, 두 이름을 $x$-유사하다고 부른다.

문자열의 길이 $x$인 접두사는 처음 $x$개의 문자이고, 길이 $x$인 접미사는 마지막 $x$개의 문자이다. 문자열보다 긴 접두사나 접미사를 구하는 연산은 잘못된 연산으로 본다.

목록에 나타나는 이름의 최대 길이까지 각 정수 $x$에 대해, $x$-유사한 이름 쌍의 개수를 구하라.

첫 줄에 정수 $n$ ($1 \le n \le 10^5$)이 주어지며, 이는 이름의 개수이다. 이어지는 $n$개의 줄에는 이름이 한 줄에 하나씩 주어진다. 모든 이름의 길이 합은 $500\,000$을 넘지 않는다. 이름은 소문자 라틴 알파벳으로 이루어지며 길이는 0이 아니다.

첫 줄에 가장 긴 이름의 길이 $m$을 출력한다. $x$ ($2 \le x \le m + 1$)번째 줄에는 $(x-1)$-유사한 이름 쌍의 개수를 출력한다.