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

1. \(A\ L\ R\ S\): Appending string \(S\) to the subarray of strings \([{A_L , A_{L+1},... A_{R-1}, A_{R}}]\). 
2. \(?\ 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.