G. Grading Papers
time limit per test
2.5 seconds
memory limit per test
32 megabytes
input
standard input
output
standard output

Please note the special memory limit for this problem.

This problem is adapted from Paper Grading.

Nearly all the students in No.84 University are asked to take a compulsory course called JL and pass the exam, which says that hundreds of students will take part in this final exam together. The teacher organizing the course is always trying to find a more efficient and fair way to grade students' test papers. In this year, you are appointed to write a program to grade papers.

Now you are given the Book of Requirement which is a dictionary consists of $$$n$$$ strings in lowercase letters, denoted by $$$s_1,s_2,\ldots,s_n$$$ in order. However, any character in the dictionary can now be changed. For example, for the string "aabbc". if we change its third character to "c", the string will become "aacbc".

The scoring criterion is given as follow. A student and his/her test paper are described as a string $$$q$$$ in lowercase letters together with two integral coefficients $$$l$$$ and $$$r$$$ . The student's final score should be the number of strings $$$s_i$$$ in the Book of Requirement with $$$l\le i \le r$$$ such that $$$s_i$$$ has a prefix equals to $$$q$$$ .

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 10^5$$$) where $$$n$$$ is the number of strings in the Book of Requirement and $$$m$$$ is the total number of modifications and students.

The following $$$n$$$ lines are $$$n$$$ non-empty strings $$$s_1,s_2,\ldots,s_n$$$ indicating all string in the book, whose total length is up to $$$10^5$$$.

Then the following $$$m$$$ lines describe all modifications and students that are asked to grade in time sequence. Each line of them starts with an integer $$$opt (1 \le opt \le 2)$$$. If $$$opt=1$$$, it follows two integers $$$i , j$$$ and one character $$$c$$$ describing a modification to replace the $$$j$$$-th character of the $$$i$$$-th string in the book with $$$c$$$, where $$$1 \le i \le n$$$ and $$$1 \le j \le len(i)$$$ . $$$len(i)$$$ means the length of $$$i$$$-th string , and $$$c$$$ is a lowercase character.

If $$$opt=2$$$ , it follows a non-empty string $$$q$$$ and two non-negative integers $$$l'$$$ and $$$r'$$$, where $$$1 \le l' \le r' \le n$$$.

To get the real $$$l$$$ and $$$r$$$ representing a student as above, you need to apply formula below

  • $$$l' = \big((l' \oplus LastAns) \bmod n\big)+1 $$$
  • $$$r' = \big((r' \oplus LastAns) \bmod n\big)+1 $$$
  • $$$l = min(l',r')$$$
  • $$$r = max(l',r')$$$

The variable $$$LastAns$$$ represents the answer obtained from the most recent operation $$$2$$$ and is initialized to $$$0$$$.

It is guaranteed that the total length of $$$q$$$ provided in the input is up to $$$10^5$$$ .

Output

For each student, output a single line containing the score of his/her test paper.

Example
Input
3 3
aaa
bbb
aac
2 aab 1 3
1 1 3 b
2 aab 1 3
Output
0
1