Background

Translated from ROI 2019 D2T4。

In the year 3019, while excavating the ancient city of Innopolis, archaeologists discovered an ancient artifact—a hard drive. It contained a file which is believed to include the texts of all ROI problems.

After studying the file, it was found that the information was encoded as a string $t$ consisting of English letters. The problem texts are very long and contain many repeated parts, so the file was stored on the hard drive in compressed form. The file is decompressed using the following algorithm:

During decompression, a string $t$ consisting of lowercase English letters will be produced. Initially, the string $t$ is empty. The compressed file contains $n$ blocks, and you must process each block in order. Each block is of one of the following two types.

• Block 1 w, where $w$ is a string. When processing such a block, append the string $w$ to the end of $t$.
• Block 2 pos len, where $pos$ and $len$ are positive integers. Assume that the characters of $t$ are numbered starting from $1$. When processing such a block, append to the end of $t$ the $len$ consecutive characters starting from position $pos$ in $t$, in order. If $len$ is large enough, some of the characters that were just appended may be used again while processing the same block.

Problem Description

The archaeologists decided to count how many times an algorithm was tested in ROI. For this, they constructed a string $p$ consisting of lowercase English letters, and they want to find the number of occurrences of this string in the decompressed string $t$.

A string $p$ of length $m$ occurs as a substring starting at position $i$ if the $m$ consecutive characters starting from the $i$-th character equal $p$. For example, the string aba occurs three times as a substring in the string ababaaba, starting at characters $1,3,6$.

Write a program to determine the number of occurrences of the given string $p$ in the decompressed string $t$.

Input Format

The first line contains two non-negative integers $m$ and $n$, representing the length of the string $p$ and the number of blocks in the compressed text, respectively.

The second line contains a non-empty string $p$, consisting of lowercase English letters.

The next $n$ lines contain the descriptions of the blocks in the format given in the Background section.

Output Format

Output one integer: the number of occurrences of the string $p$ in the text.

3 4
aba
1 ab
2 1 3
2 3 3
2 1 8

6

Hint

Sample Explanation:

The decompression process of $t$ is as follows:

aba occurs $6$ times in ababaabaababaaba.

Constraints:

Let the length of the string after decompressing the first $i$ blocks be $L_i$, and let the type of the $i$-th block be $type_i$.

For $100\%$ of the testdata, $\sum w\leq 2\times 10^5$。

Translated by ChatGPT 5