You are given an array \(A\) of \(N\) strings and \(Q\) operations where each operation is one of the following two types:

\(A\ L\ R\ S\): Appending string \(S\) to the subarray of strings \([{A_L , A_{L+1},... A_{R-1}, A_{R}}]\).
\(?\ L\ R\ T\): Finding the frequency of the string T in subarrays \([{A_L ,A_{L+1},...A_{R-1},A_{R}}]\).

Input format

The first line contains two integers \(N\) and \(Q\) which is the length of \(A\) and the number of operations respectively.
The second line contains \(N\) space-separated strings describing the content of \(A\).
Each of the next \(Q\) lines contain the descriptions of each operation.

Output format

For each operation of the second type, print the answer in a separate line.

Constraints

1 ≤ \(N\) ≤ 10⁵

1 ≤ \(Q\) ≤ 10⁵

1 ≤ L ≤ R ≤ \(N\)

\(1 \leq |A_i| , |T|, |S| \leq 10^5\), where 1 ≤ \(i\) ≤ \(N\)

It is guaranteed that the total sum of lengths of the input strings does not exceed 1e6 characters and all input characters are lowercase English characters.
It is guaranteed that there is at least one and at most a hundred operations of the second type.