409243: GYM103466 F Paper Grading

The story is purely fictitious.

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,\cdots,s_n$$$ in order. However, the book as a magic item may be modified with exchanges. It is possible to swap the positions of two strings inside the dictionary at any time. For instance, if one swap the first and the fifth strings, the so-called first string in this dictionary after the modification would be the fifth one originally.

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 three integral coefficients $$$k,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 the longest common prefix of $$$q$$$ and $$$s_i$$$ is of length at least $$$k$$$.

The first line contains two integers $$$n$$$ and $$$m~(1\leq n,m \leq 2\times 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,\cdots,s_n$$$ indicating all string in the book, whose total length is up to $$$2\times 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\leq opt\leq 2)$$$. If $$$opt=1$$$, it follows two integers $$$i$$$ and $$$j$$$ describing a modification to swap the $$$i$$$-th and the $$$j$$$-th string in the book, where $$$1\leq i,j\leq n$$$ and $$$i$$$ can be equal to $$$j$$$. If $$$opt=2$$$, it follows a non-empty string $$$q$$$ and three non-negative integers $$$k,l$$$ and $$$r$$$, where $$$0\leq k\leq |q|$$$ and $$$1\leq l \leq r \leq n$$$, representing a student as above.

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

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

3 4
aaa
bbb
aac
2 aasdd 2 1 3
2 aab 1 1 2
1 2 3
2 aat 2 1 2

2
1
2

In the example, the initial Book of Requirement consists of $$$s_1$$$=aaa, $$$s_2$$$=bbb and $$$s_3$$$=aac. For the first given student with the string $$$q$$$=aasdd, the longest common prefixes with aaa and aac are of length at least $$$2$$$. Hence his final score is $$$2$$$. For the second student, the only available string to consider in the book is the first one $$$s_1$$$=aaa.

Then a modification comes, and strings in the Book of Requirement become $$$s_1$$$=aaa,$$$s_2$$$=aac and $$$s_3$$$=bbb. For the third student, both $$$s_1$$$ and $$$s_2$$$ have a common prefix with given $$$q$$$=aat of length $$$2$$$. Hence the answer is $$$2$$$.