You are given a string \(S\) of length \(N\) consisting of only lower case English alphabets. You will need to answer \(Q\) queries of the following types.

• \(1 \ L \ R \ W\): Find the number of occurrences of string \(W\) in substring \([L,R]\) of string \(S\).
• \(1 \ L \ R \ U\): Update the substring \([L,R]\) of string \(S\) with string \(U\).

Input format

• The first line contains two space-separated integers \(N\) and \(Q\).
• The second line contains a string \(S\) of length \(N\).
• Next \(Q\) lines contains queries of two types as given in the problem statement.

Output format

For each query of \(type \ 1\):

• You are required to print the number of occurrences of string \(W\) in substring \([L,R]\) of string \(S\) in a new line.

Constraints

\(1\le N\le 10^5\)

\(1\le L\le R\le N\)

\(|W|\le min(R-L+1,10)\)

\(|U|=R-L+1\)

\(\sum_{i=1}^{Q} |W|\le 10^6\)

\(\sum_{i=1}^{Q} |U|\le 10^5\)