You are given a log file in the form of a single string \(S\) of length \(N\). You are also given \(Q\) queries. There are two types of queries:

1. You are given a string \(W\). Therefore, perform a substring search for string \(W\) in the log file and print the count of occurrences for this string in the file.
2. You are given \(L\), \(R\), and a string \(W\) of length \(R-L+1\). Update the log string indexed from \(L\) to \(R\) to string \(W\).

Input format

• The first line contains two integers \(N\) and \(Q\).
• The second line contains a string \(S\).
• Next \(Q\) lines contain one of the two queries mentioned in the problem statement.
  • For the first type of query, you will be given \(1\ W\).
  • For the second type of query, you will be given \(2\ L\ R\ W\).

Output format

For the query of type 1, you are required to print the count of occurrences of string \(S\) in a new line.4.

Constraints

\(1 \le  N,Q \le 10^5\\ 1 \le L\le R \le N\\ |W| \le N\\ S\ contains\ lower\ case\ alphabets\\ Sum\ of\ lengths\ of\ W \le 10^5\)