The year is 3019. During excavations of the ancient city of Innopolis, archaeologists discovered an artifact — a hard drive containing a file that presumably holds the texts of all problems from the All-Russian Olympiad in Informatics.
After examining the file, it was determined that the information is encoded such that the text recorded in the file is a string $t$ consisting of lowercase English letters. The problem text turned out to be quite long and contained many repetitions, so the file was stored on the disk in a compressed form. The following algorithm is used to decompress it.
During decompression, a string $t$ of lowercase English letters is formed. Initially, the string is empty. The compressed file consists of $n$ blocks that must be processed in order. Each block is of one of two types:
- Block "1 $w$", where $w$ is a string. When processing such a block, the string $w$ is appended to the end of string $t$.
- Block "2 $pos$ $len$", where $pos$ and $len$ are positive integers. Let the characters of string $t$ be 1-indexed. When processing such a block, $len$ consecutive characters of string $t$, starting from position $pos$, are appended to the end of string $t$ one by one. Note that if $len$ is sufficiently large, some of the characters just appended may be used again while processing the same block.
Scientists want to find out how many times a certain idea appeared in the Olympiads. To do this, they formed a string $p$ of lowercase English letters and want to find the number of occurrences of string $p$ as a substring in the string $t$ obtained after decompressing the file.
A string $p$ of length $m$ occurs in string $t$ as a substring starting at position $i$ if the $m$ consecutive characters of string $t$ starting from the $i$-th position represent the string $p$. For example, the string "aba" occurs as a substring in the string "ababaaba" three times: at positions 1, 3, and 6.
You are required to write a program that determines the number of occurrences of the given string $p$ in the string $t$ obtained after decompressing the file.
Input
The first line contains natural numbers $m$ and $n$ — the length of string $p$ and the number of blocks in the compressed text ($1 \leqslant m \leqslant 2 \cdot 10^5$, $1 \leqslant n \leqslant 10^4$).
The second line of the input contains a non-empty string $p$ consisting of lowercase English letters.
The next $n$ lines contain descriptions of the blocks in the format described in the problem. For blocks of the first type, the appended string $w$ is non-empty, and the sum of the lengths of all strings $w$ in blocks of the first type does not exceed $2 \cdot 10^5$. For blocks of the second type, at the moment of processing this block, string $t$ contains at least $pos$ characters. The length of the decompressed text does not exceed $10^{15}$ characters.
Output
Output a single integer — the number of occurrences of string $p$ in the text.
Scoring
Let $L_i$ be the length of the text $t$ after processing $i$ blocks. Let $type_i$ be the type of the $i$-th block. If $type_i = 2$, let $pos_i$ and $len_i$ be the parameters of this block.
| Subtask | Points | Constraints | Additional Constraints | Dependencies |
|---|---|---|---|---|
| 1 | 6 | $m \leqslant 2000, n = 1$ | $L_n \leqslant 1000$ | |
| 2 | 10 | $m \leqslant 10^5, n \leqslant 2000$ | $L_n \leqslant 10^6$ | 1 |
| 3 | 10 | $m \leqslant 2000, n \leqslant 2000$ | $L_n \leqslant 10^{10}$, except first block $type_i=2, pos_i=1, len_i \vdots L_1$ | 1 |
| 4 | 10 | $m \leqslant 2000, n \leqslant 2000$ | $L_n \leqslant 10^{10}, pos_i = L_{i-1}$ | 1 |
| 5 | 10 | $m \leqslant 20, n \leqslant 2000$ | $L_n \leqslant 10^{10}, pos_i = 1, len_i \leqslant 10^7$ | |
| 6 | 4 | $m \leqslant 2000, n \leqslant 2000$ | $L_n \leqslant 10^{10}, pos_i = 1, len_i \leqslant 10^7$ | 1, 5 |
| 7 | 10 | $m \leqslant 20, n \leqslant 20$ | $L_n \leqslant 10^{10}, p \in \{'a'\}, pos_i + len_i - 1 \leqslant L_{i-1}$ | |
| 8 | 6 | $m \leqslant 20, n \leqslant 20$ | $L_n \leqslant 10^{10}, pos_i + len_i - 1 \leqslant L_{i-1}$ | 7 |
| 9 | 2 | $m = 1, n \leqslant 2000$ | $L_n \leqslant 10^{10}, p \in \{'a'\}$ | |
| 10 | 4 | $m \leqslant 20, n \leqslant 2000$ | $L_n \leqslant 10^{10}, p \in \{'a'\}$ | 7–9 |
| 11 | 5 | $m \leqslant 20, n \leqslant 2000$ | $L_n \leqslant 10^{10}$ | 5, 7–10 |
| 12 | 14 | $m \leqslant 10^5, n \leqslant 2000$ | $L_n \leqslant 10^{10}$ | 1–11 |
| 13 | 9 | $m \leqslant 2 \cdot 10^5, n \leqslant 10000$ | $L_n \leqslant 10^{15}$ | 1–12 |
Examples
Input 1
3 4 aba 1 ab 2 1 3 2 3 3 2 1 8
Output 1
6
Note
During the decompression of the file in the example, the following strings are obtained sequentially: "" $\to$ "ab" $\to$ "ababa" $\to$ "ababaaba" $\to$ "ababaabaababaaba".
The string "aba" occurs as a substring in the resulting string "ababaabaababaaba" 6 times.