这个故事纯属虚构。

No.84 大学的几乎所有学生都被要求修读一门名为 JL 的必修课并通过考试，这意味着数百名学生将一起参加这次期末考试。组织这门课程的老师一直在努力寻找一种更高效、更公平的方式来批改学生的试卷。今年，你被指派编写一个程序来批改试卷。

现在你拥有“需求手册”（Book of Requirement），这是一个由 $n$ 个小写字母字符串组成的字典，按顺序记为 $s_1, s_2, \dots, s_n$。然而，作为一件魔法物品，这本手册可以通过交换进行修改。在任何时候，都可以交换字典中两个字符串的位置。例如，如果交换第一个和第五个字符串，修改后字典中所谓的“第一个”字符串就是原来第五个字符串。

评分标准如下：一名学生及其试卷由一个由小写字母组成的字符串 $q$ 以及三个整数系数 $k, l$ 和 $r$ 描述。学生的最终得分应该是“需求手册”中满足 $l \le i \le r$ 且 $q$ 与 $s_i$ 的最长公共前缀长度至少为 $k$ 的字符串 $s_i$ 的数量。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 2 \times 10^5$)，其中 $n$ 是“需求手册”中字符串的数量，$m$ 是修改和学生考试的总数。

接下来的 $n$ 行包含 $n$ 个非空字符串 $s_1, s_2, \dots, s_n$，表示手册中的所有字符串，其总长度不超过 $2 \times 10^5$。

随后的 $m$ 行按时间顺序描述了所有的修改和学生考试。每行以一个整数 $opt$ ($1 \le opt \le 2$) 开头。如果 $opt = 1$，后面跟着两个整数 $i$ 和 $j$，描述一次交换手册中第 $i$ 个和第 $j$ 个字符串的修改，其中 $1 \le i, j \le n$，$i$ 可以等于 $j$。如果 $opt = 2$，后面跟着一个非空字符串 $q$ 和三个非负整数 $k, l$ 和 $r$，其中 $0 \le k \le |q|$ 且 $1 \le l \le r \le n$，表示如上所述的一名学生。

保证输入中提供的 $q$ 的总长度不超过 $2 \times 10^5$。

输出格式

对于每名学生，输出一行，包含其试卷的得分。

样例

输入 1

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

输出 1

2
1
2

说明

在样例中，初始的“需求手册”包含 $s_1=\text{aaa}, s_2=\text{bbb}$ 和 $s_3=\text{aac}$。对于第一个学生，字符串 $q=\text{aasdd}$ 与 $\text{aaa}$ 和 $\text{aac}$ 的最长公共前缀长度至少为 $2$。因此他的最终得分为 $2$。对于第二个学生，手册中唯一需要考虑的字符串是第一个 $s_1=\text{aaa}$。

随后发生了一次修改，手册中的字符串变为 $s_1=\text{aaa}, s_2=\text{aac}$ 和 $s_3=\text{bbb}$。对于第三个学生，$s_1$ 和 $s_2$ 与给定的 $q=\text{aat}$ 的公共前缀长度均为 $2$。因此答案为 $2$。