Description

Given $n$ strings $s_1, s_2, \ldots, s_n$ consisting of lowercase letters, find the number of distinct substrings (excluding the empty string).

Furthermore, let $Q$ be the minimal DFA that can accept all suffixes of $s_1, s_2, \dots, s_n$. Please output the number of states in $Q$. (If you cannot understand this sentence, you may treat it as outputting the number of states of the "generalized suffix automaton" built from $s_1, s_2, \dots, s_n$.)

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain a string. The $i$-th line represents the string $s_{i-1}$.

Output Format

The first line contains a positive integer: the number of distinct substrings.

The second line contains a positive integer: the number of states in $Q$.

4
aa
ab
bac
caa

10
10

1
a

1
2

Hint

Constraints: $1 \le n \le 4 \cdot 10^5$, $1 \le \sum{|s_i|} \le 10^6$.

Sample 1 explanation: There are $10$ distinct substrings: "a","b","c","aa","ab","ac","ba","ca","bac","caa". The DFA structure is omitted.

Sample 2 explanation: There is $1$ distinct substring: "a". The DFA contains a start state $S$ and a state $T$, with an edge $S \to T$ labeled a. Therefore, the total number of states is $2$.

Translated by ChatGPT 5