Description

给定 $n$ 个由小写字母组成的模板串 $S_{1...n}$，$q$ 组询问，询问分为以下两种类型：

1. 1 T：给定一个由小写字母组成的询问串 $T$。
2. 2 p l r：设 $num(p,l,r)$ 表示 $S_p$ 的 $[l,r]$ 子串是多少个询问串的子串，求 $\max\limits_{i=1}^{l}(num(p,i,r))$。

Input Format

第一行，两个数 $n,q,w_0$，其中 $w_0$ 表示数据类型。

• $w_0=0$：

  第 $2\sim n+1$ 行，每行一个字符串，第 $i+1$ 行表示 $S_i$。

  接下来 $q$ 行，每行一组询问，格式如题。

• $w_0=1$：

  第二行，输入三个整数 $A,B,C$。

  接下来 $n$ 行，每行一个字符串，表示一个模板串。

  接下来，询问按照如下代码生成（代码中的 lst 表示上一次询问 $2$ 的答案，初始时为 $0$，le[i] 表示模板串 $i$ 的长度，s 是 char 数组）：

while (q--) {
	int op;
	scanf("%d", &op);
	if (op == 1) {
		scanf("%s", s + 1);
		int x((1ll * A * lst + B) % C), l(strlen(s + 1));
		for (int i(1); i <= l; ++i) {
			swap(s[i], s[x % l + 1]);
			x = (1ll * A * x + B) % C;
		}
	} else {
		int p, l, r;
		scanf("%d%d%d", &p, &l, &r);
		int x((1ll * A * lst + B) % C);
		p = (p + x) % n + 1;
		x = (1ll * A * x + B) % C;
		l = (l + x) % le[p] + 1;
		x = (1ll * A * x + B) % C;
		r = (r + x) % le[p] + 1;
		if (l > r) swap(l, r);
		// 此处更新 lst
	}
}

Output Format

对于每个询问 $2$，输出一行一个整数表示答案。

5 11 0
abb
aab
baab
bbaa
aabbb
1 ab
2 1 1 3
2 2 2 3
1 ba
2 3 1 2
2 4 1 2
2 4 2 3
1 abb
2 5 2 4
2 1 1 3
2 1 1 2

0
1
1
0
1
1
1
2

5 11 1
114 514 1919810
abb
aab
baab
bbaa
aabbb
1 ab
2 1 1 3
2 2 2 3
1 ba
2 3 1 2
2 4 1 2
2 4 2 3
1 abb
2 5 2 4
2 1 1 3
2 1 1 2

0
0
1
0
0
1
1
0

Hint

对于 $100\%$ 数据：$1\le n,q\le 10^5$，$\sum\limits_{i=1}^{n}|S_i|\le5\times10^5$，$\sum|T|\le5\times10^5$，$1\le p\le n$，$w_0\in\{0,1\}$，$1\le A,B<C\le10^9$。

测试点 $8\sim 17$ 保证对于所有询问 $2$，$l=1$。