Text Editor Find and Replace

You are given a text editor that stores a file as a string a of length n. Additionally, you are provided with a dictionary of m words, denoted as s₁, s₂, ..., s_m.

The text editor supports two operations:

• Find Operation: Given two 1-indexed parameters l and r, consider the substring $$a[l:r]$$ (i.e. from index l to r inclusive). For each dictionary word s_i, let \(\mathrm{occur}(s_i, a[l:r])\) denote the number of times s_i occurs in this substring (overlapping occurrences are counted). The answer to the query is $$\sum_{i=1}^{m} \mathrm{occur}(s_i, a[l:r]).$$
• Replace Operation: Given three parameters l, r and a string t, replace the substring $$a[l:r]$$ with the first \(r-l+1\) characters of an infinite repetition of t. For example, if replacing the substring Mds72SKsLL with the infinitely repeated string of Rabb, the replacement becomes RabbRabbRa.

You will be given q queries. Each query is either a Find or a Replace operation. You need to output the answer for each Find operation.

inputFormat

The input begins with a line containing the initial string a.

The next line contains an integer m (the number of dictionary words).

The following m lines each contain a dictionary word s_i.

The next line contains an integer q, the number of queries.

Each of the next q lines describes a query in one of the following formats:

• 1 l r — a Find operation.
• 2 l r t — a Replace operation, where t is the replacement string.

Note that the indexing is 1-indexed.

outputFormat

For each Find query, output a single integer on a new line representing the sum of occurrences of all dictionary words in the specified substring.

sample

abcdabc
2
ab
abc
4
1 1 7
2 5 7 xy
1 1 7
1 3 5

4
2
0