아이디어 찾기

3019년 고대 도시 이노폴리스에서 고고학자들이 하드 디스크를 발견했다. 이 디스크에는 전 러시아 정보올림피아드 문제 본문이 모두 들어 있을 것으로 추정되는 파일이 있다.

파일을 조사해 보니, 내용은 영문 소문자로 이루어진 문자열 $t$로 부호화되어 있었다. 문제 본문은 꽤 길고 반복이 많아서, 파일은 압축된 상태로 디스크에 저장되어 있었다. 압축을 풀 때는 다음 알고리즘을 쓴다.

압축 해제 과정에서 영문 소문자로 이루어진 문자열 $t$가 만들어진다. 처음에는 빈 문자열이다. 압축 파일은 $n$개의 블록으로 이루어져 있고, 순서대로 처리해야 한다. 각 블록은 두 가지 종류 중 하나이다.

• 블록 1 $w$: 여기서 $w$는 문자열이다. 이 블록을 처리하면 $w$를 $t$의 끝에 붙인다.
• 블록 2 $pos$ $len$: 여기서 $pos$와 $len$은 양의 정수이다. $t$의 문자는 1번부터 번호를 매긴다. 이 블록을 처리하면 $t$의 $pos$번째 문자부터 연속한 $len$개의 문자를 하나씩 차례로 $t$의 끝에 붙인다. $len$이 충분히 크면, 방금 붙인 문자가 같은 블록을 처리하는 동안 다시 사용될 수 있다.

연구진은 어떤 아이디어가 올림피아드에서 몇 번 등장했는지 알고 싶다. 영문 소문자로 이루어진 문자열 $p$를 만들고, 압축을 푼 문자열 $t$에 $p$가 부분 문자열로 몇 번 나오는지 센다.

길이 $m$인 문자열 $p$가 $i$번째 문자에서 시작해 $t$에 나온다는 것은, $t$의 $i$번째 문자부터 연속한 $m$개의 문자가 $p$를 이룬다는 뜻이다. 예를 들어 aba는 ababaaba에 세 번 나온다. 위치는 1, 3, 6이다.

압축을 푼 문자열 $t$에서 $p$가 나오는 횟수를 세는 프로그램을 작성하라.

첫 줄에 자연수 $m$과 $n$이 주어진다. $m$은 문자열 $p$의 길이이고, $n$은 압축 텍스트의 블록 수이다 ($1 \le m \le 2 \cdot 10^5$, $1 \le n \le 10^4$).

둘째 줄에는 비어 있지 않은 문자열 $p$가 주어진다. $p$는 영문 소문자로만 이루어진다.

다음 $n$개의 줄에는 위 형식의 블록이 한 줄에 하나씩 주어진다. 첫 번째 종류 블록의 문자열 $w$는 비어 있지 않고, 첫 번째 종류 블록에 있는 모든 $w$의 길이 합은 $2 \cdot 10^5$을 넘지 않는다. 두 번째 종류 블록을 처리할 때, $t$에는 이미 $pos$개 이상의 문자가 있다. 압축을 푼 텍스트의 길이는 $10^{15}$을 넘지 않는다.

문자열 $p$가 텍스트에 나타나는 횟수를 나타내는 정수 하나를 출력한다.

예시 파일을 풀면 다음 문자열이 차례로 나온다. 빈 문자열 $\to$ ab $\to$ ababa $\to$ ababaaba $\to$ ababaabaababaaba.

문자열 aba는 ababaabaababaaba에 6번 나온다.