시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 256 MB 24 14 12 54.545%

문제

K. has stumbled upon a weird game while playing on his computer. The game consists of an initial string S of length N (1 ≤ N ≤ 1000) and an empty set T. The following events might occur during the game:

  • a character is added at the end of S, thus increasing its length by 1
  • the string S is added to the set T
  • the game master inquires: “How many strings in T are suffixes of S?”. A suffix of S is a substring which can start at any position in S, but must finish on the last position of S.

Because K. wants to go visit a famous castle near his hometown, you must help him deal with the game as quickly as possible.

입력

The first line of the input contains two integers: N, the length of the initial string S and E, the number of events (E ≤ 1200000).

The second line describes the string S; the string consists only of lowercase Roman alphabet (a-z).

The following E lines describe the events. Each of these lines contains an integer p, describing the event type.

If p is 1, then it is followed by a character (a-z), which will be added at the end of S.
If p is 2, then the string S is added in T.
If p is 3, then you must respond to the query “How many strings in T are suffixes of the current S?”

출력

The output should consist of a line containing an integer for each type 3 event in the input, which represents the answer to the query.

Note: T is a set, so it doesn't contain duplicates.

Note: Large input: for C scanf and printf recommended; for C++, add “cin.tie(NULL);
ios::sync_with_stdio(false);
” before reading; for Java use BufferedReader and BufferedWriter.

예제 입력 1

1 11
a
2
1 b
1 a
2
2
1 c
1 a
3
1 b
1 a
3

예제 출력 1

1
2