#742 Floccinaucinihilipilification

문제

지문 언어

$N$ 종류의 바이러스로 이루어진 생태계가 있다. 각 바이러스의 구조는 영대문자로 이루어진 문자열 $V_i$ 로 나타낸다. 구조가 같아도 서로 다른 종류의 바이러스는 구별한다.

두 바이러스의 유사도는 구조를 나타내는 두 문자열의 최장 공통 접두사의 길이이다. 생태계의 멸종 위험도는 서로 다른 두 종류의 바이러스를 고르는 모든 순서 없는 쌍에 대해 유사도를 합한 값이다.

생태계에 $M$ 번의 변화가 순서대로 일어난다. 각 변화는 영대문자 $c$ 와 한 자리 숫자 $x$ 를 이어 붙인 $cx$ 로 나타내며, 다음 순서대로 적용한다.

현재 존재하는 모든 바이러스의 구조를 동시에 바꾼다. 구조가 $c$ 로 시작하면 맨 앞의 문자 하나를 제거하고, 그렇지 않으면 맨 앞에 $c$ 를 추가한다.
구조가 한 글자 문자열 $c$ 인 새로운 바이러스 $x$ 종류를 추가한다. 새 바이러스들은 서로 다른 종류이며, 기존 바이러스와도 구별한다.

문자를 제거한 결과 빈 문자열이 될 수 있다. 빈 문자열은 어떤 문자로도 시작하지 않으며, 다른 문자열과의 유사도는 $0$ 이다. 새로 추가된 바이러스도 이후의 모든 변화에 참여한다.

각 변화 이후, 현재 존재하는 모든 바이러스로 계산한 멸종 위험도와 처음에 주어진 $N$ 종류의 바이러스만으로 계산한 멸종 위험도의 차의 절댓값을 구하여라. 두 값을 계산할 때에는 모두 해당 시점의 구조를 사용한다.

입력은 다음과 같은 형식으로 주어진다.

$N$ $V_1$ $V_2$

$M$ 개의 정수를 공백으로 구분하여 한 줄에 출력한다. $i$ 번째 정수는 $i$ 번째 변화 이후 두 멸종 위험도의 차의 절댓값이다.

#	점수	제한
1	6	$N,M,\sum_{i=1}^{N}\|V_i\| \leq 10$ .

예제 1

입력

2
A
B
3
A2A0B1

출력

3 0 6

첫 번째 변화 이후 처음의 두 바이러스의 구조는 각각 빈 문자열과 $\text{AB}$ 가 된다. 새 바이러스 두 종류의 구조는 모두 $\text{A}$ 이다. 전체 멸종 위험도는 $3$ 이고 처음의 두 바이러스만으로 계산한 값은 $0$ 이다.

두 번째 변화 이후 구조는 차례대로 $\text{A}$ , , 빈 문자열, 빈 문자열이다. 두 멸종 위험도는 모두 이다.