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.