Floccinaucinihilipilification

An ecosystem initially contains $N$ distinct types of viruses. The structure of virus $i$ is represented by an uppercase English string $V_i$. Viruses of different types remain distinct even if their structures are identical.

The similarity of two viruses is the length of the longest common prefix of their structure strings. The extinction risk of an ecosystem is the sum of these similarities over all unordered pairs of distinct virus types.

The ecosystem undergoes $M$ changes in order. Each change is represented by an uppercase letter $c$ followed by one digit $x$, written as $cx$. Apply a change in the following order.

• Simultaneously modify every virus currently present. If its structure starts with $c$, remove exactly the first character. Otherwise, prepend $c$ to its structure.
• Add $x$ new virus types, each with the one-character structure $c$. These new types are distinct from one another and from all existing types.

Removing a character may produce an empty string. An empty string does not start with any letter and has similarity $0$ with every string. Newly added viruses participate in all subsequent changes.

After each change, find the absolute difference between the extinction risk computed using all virus types currently present and the extinction risk computed using only the original $N$ virus types. Both risks use the structures at that point in time.

The input is given in the following format:

$N$ $V_1$ $V_2$

Print $M$ space-separated integers on one line. The $i$-th integer must be the absolute difference between the two extinction risks after change $i$.

• $2 \leq N \leq 300\,000$.
• $1 \leq |V_i|$ ().