{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe story is purely fictitious.\u003c/p\u003e\n\u003cp\u003eNearly 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\u0027 test papers. In this year, you are appointed to write a program to grade papers.\u003c/p\u003e\n\u003cp\u003eNow 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.\u003c/p\u003e\n\u003cp\u003eThe 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\u0027s 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$.\u003c/p\u003e\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003eThe 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.\u003c/p\u003e\n\u003cp\u003eThe 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$.\u003c/p\u003e\n\u003cp\u003eThen 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\u003d1$, 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\u003d2$, 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.\u003c/p\u003e\n\u003cp\u003eIt is guaranteed that the total length of $q$ provided in the input is up to $2\\times 10^5$.\u003c/p\u003e\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eFor each student, output a single line containing the score of his/her test paper.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 4\naaa\nbbb\naac\n2 aasdd 2 1 3\n2 aab 1 1 2\n1 2 3\n2 aat 2 1 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1\n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e\u003cp\u003eIn the example, the initial Book of Requirement consists of $s_1\u003d aaa ,s_2\u003d bbb $ and $s_3\u003daac$. For the first given student with the string $q\u003daasdd$, 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\u003daaa$.\u003c/p\u003e\u003cp\u003eThen a modification comes, and strings in the Book of Requirement become $s_1\u003daaa,s_2\u003daac$ and $s_3\u003dbbb$. For the third student, both $s_1$ and $s_2$ have a common prefix with given $q\u003daat$ of length $2$. Hence the answer is $2$.\u003c/p\u003e"}}]}