Idea Search

In the year 3019, archaeologists dug up an ancient city called Innopolis and found a hard disk. It holds a file that probably contains the texts of all problems from the All-Russian informatics olympiads.

After studying the file, they found that its contents encode a string $t$ of lowercase English letters. The problem texts are quite long and contain many repetitions, so the file was stored on disk in compressed form. The following algorithm unpacks it.

During unpacking, a string $t$ of lowercase English letters is built. It starts empty. The compressed file consists of $n$ blocks, which must be processed in order. Each block has one of two types.

• Block 1 $w$, where $w$ is a string. Processing this block appends $w$ to the end of $t$.
• Block 2 $pos$ $len$, where $pos$ and $len$ are positive integers. Number the characters of $t$ starting from 1. Processing this block appends, one by one, $len$ consecutive characters of $t$ starting at position $pos$ to the end of $t$. If $len$ is large enough, some of the characters just appended may be used again while processing the same block.

The researchers want to know how many times an idea appeared in the olympiads. They form a string $p$ of lowercase English letters and count how many times $p$ occurs as a substring of the unpacked string $t$.

A string $p$ of length $m$ occurs in $t$ starting at position $i$ if the $m$ consecutive characters of $t$ starting at the $i$-th character form $p$. For example, aba occurs in ababaaba three times, at positions 1, 3, and 6.

Write a program that counts the occurrences of $p$ in the unpacked string $t$.

The first line contains natural numbers $m$ and $n$, the length of string $p$ and the number of blocks in the compressed text ($1 \le m \le 2 \cdot 10^5$, $1 \le n \le 10^4$).

The second line contains the nonempty string $p$, which consists of lowercase English letters.

Each of the next $n$ lines describes one block in the format above. For blocks of the first type, the appended string $w$ is nonempty, and the total length of all strings $w$ in blocks of the first type does not exceed $2 \cdot 10^5$. For blocks of the second type, when the block is processed, $t$ already has at least $pos$ characters. The length of the unpacked text does not exceed $10^{15}$ characters.

Print one integer, the number of occurrences of the string $p$ in the text.

Unpacking the example file produces these strings in turn: empty string $\to$ ab $\to$ ababa $\to$ ababaaba $\to$ ababaabaababaaba.

The string aba occurs in ababaabaababaaba 6 times.