Another ICPC String Problem

Input

The first line of the input contains $2$ integers $n,q$ (1 \leq n \leq 5\times 10^4, 1 \leq q \leq 10^5).

The second line of the input contains a string $s$ of length $n$ consisting of lowercase Latin characters.

$q$ lines follow, which may have one of the following formats:

1. If it's a query of the first type, it will contain an integer k_i (1 \leq k_i \leq n) and a lowercase character c_i, which means that character s_{k_i} becomes c_i

2. If it's a query of the second type, it will contain a $0$ followed by a nonempty string $p$ of lowercase characters, meaning that you should find the number of times that $p$ occurs as a substring of $s$.

It is guaranteed that there is at least one query of type $2$.

It is guaranteed that the sum of lengths of strings $p$ over all queries of the type $2$ doesn't exceed 5\cdot 10^4.

Output

For each operation of type $2$ output the number of times that the query string appears as a substring of $s$.

Examples