작은 문자열 개수 세기

$n$개의 문자열로 이루어진 집합 $D$와 문자열 $s$가 주어진다. $D$에 있는 문자열 중 사전순으로 $s$보다 작은 문자열의 개수를 구하라.

문자열 $s$는 $q$번 수정된다. 각 수정은 정수 $k_i$와 문자 $c_i$의 쌍으로 주어진다. 수정 $(k_i, c_i)$는 $s$의 $k_i$번째 문자부터 끝까지 모든 문자를 $c_i$로 바꾼다.

예를 들어 초기 문자열이 anatoly이고 수정 $(5, \mathtt{o})$, $(3, \mathtt{b})$, $(7, \mathtt{x})$를 차례로 적용하면, 문자열은 anatoly → anatooo → anbbbbb → anbbbbx로 바뀐다.

각 수정 후에 현재 $s$보다 사전순으로 작은 $D$의 문자열 개수를 출력한다.

첫 줄에 정수 $n$과 $q$가 주어진다 ($1 \le n, q \le 10^6$). 둘째 줄에는 문자열 $s$가 주어지며, 길이는 $10^6$ 이하의 소문자 알파벳이다. 이어서 $n$개의 줄에 $D$의 문자열이 주어진다. 각 문자열은 소문자 알파벳으로 이루어지며, $D$에 있는 문자열 길이의 합은 $10^6$을 넘지 않는다. 마지막으로 $q$개의 줄에 수정이 주어진다. 각 줄에는 정수 $k_i$와 소문자 알파벳 $c_i$가 공백으로 구분되어 있다 ($1 \le k_i \le |s|$).

첫 줄에 초기 문자열 $s$보다 사전순으로 작은 $D$의 문자열 개수를 출력한다. 이어서 $q$개의 줄에 각 수정 후의 답을 한 줄씩 출력한다.

첫 번째 테스트에서 문자열은 anatoly → anatooo → anbbbbb → anbbbbx로 바뀐다.

초기 문자열 anatoly는 집합의 모든 문자열보다 작으므로 답은 $0$이다. 첫 수정 후의 anatooo는 집합에 같은 문자열이 있지만 그보다 작지 않으므로 답은 여전히 $0$이다. 두 번째 수정 후의 anbbbbb는 anatooo와 anba보다 크고 anbbbbu와 boris보다 작으므로 답은 $2$이다. 마지막 수정 후의 anbbbbx는 anatooo, anba, anbbbbu보다 크므로 답은 $3$이다.