성

시간 제한0.5초메모리 제한256 MB

요약

문자열에 문자가 덧붙고 현재 문자열이 집합에 추가되는 과정에서, 저장된 문자열 중 현재 문자열의 접미사인 것의 개수를 묻는 질의에 답한다.

난이도: 보통10점 중 7점
유형: 문자열, 트라이
정답자: 아직 제출이 없습니다

문제

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를 쓰면 된다.

예제8

예제 1

입력

예상 출력

1
2

예제 2
입력
```
1 1
a
3
```
예상 출력
```
0
```
예제 3
입력
```
1 2
a
2
3
```
예상 출력
```
1
```
예제 4
입력
```
3 6
abc
2
2
2
3
1 c
3
```
예상 출력
```
1
0
```
예제 5
입력
```
5 8
abcde
2
1 f
2
1 g
2
1 h
1 i
3
```
예상 출력
```
0
```
예제 6
입력
```
3 8
aaa
2
3
1 a
3
2
3
1 a
3
```
예상 출력
```
1
1
2
2
```

예제 7

입력

예상 출력

2
2
2

예제 8

입력

4 10
abab
2
1 c
2
1 a
1 b
1 a
1 b
3
1 c
3

예상 출력

1
1