성

K는 컴퓨터로 놀다가 이상한 게임을 하나 발견했다. 게임은 길이가 $N$인 문자열 $S$와 비어 있는 집합 $T$로 시작한다 ($1 \le N \le 1000$). 게임이 진행되는 동안 다음 세 가지 사건이 일어난다.

• $S$의 끝에 문자 하나가 붙어서 $S$의 길이가 1 늘어난다.
• 지금의 $S$를 집합 $T$에 넣는다.
• 게임 진행자가 묻는다. "$T$에 들어 있는 문자열 가운데 $S$의 접미사인 것은 몇 개인가?" $S$의 접미사는 $S$의 어느 위치에서 시작해도 되지만 반드시 $S$의 마지막 위치에서 끝나는 부분문자열이다.

K는 고향 근처에 있는 유명한 성을 보러 가고 싶어 한다. K가 게임을 최대한 빨리 끝내도록 도와라.

첫째 줄에 정수 두 개 $N$과 $E$가 주어진다. $N$은 처음 문자열 $S$의 길이이고, $E$는 사건의 개수이다 ($E \le 1\,200\,000$).

둘째 줄에 문자열 $S$가 주어진다. $S$는 알파벳 소문자 a-z로만 이루어져 있다.

이어지는 $E$개의 줄에 사건이 한 줄에 하나씩 주어진다. 각 줄은 사건의 종류를 나타내는 정수 $p$로 시작한다.

• $p$가 1이면 뒤에 문자 하나(a-z)가 이어진다. 이 문자를 $S$의 끝에 붙인다.
• $p$가 2이면 지금의 $S$를 $T$에 넣는다.
• $p$가 3이면 "$T$에 들어 있는 문자열 가운데 지금의 $S$의 접미사인 것은 몇 개인가?"라는 질문에 답해야 한다.

입력에 있는 종류 3의 사건마다 그 답을 정수로 한 줄에 하나씩 출력한다.

$T$는 집합이므로 같은 문자열을 여러 번 넣어도 하나만 들어 있다.

입력이 매우 크므로 빠른 입출력이 필요하다. C에서는 scanf와 printf를, C++에서는 읽기 전에 cin.tie(NULL); ios::sync_with_stdio(false);를, 자바에서는 BufferedReader와 BufferedWriter를 쓰면 된다.