题目背景

教皇内侍已经感觉到了身体上的疼痛。疼痛迅速传遍了全身，让他想抓想挠。

不要忘记耶稣所遭受的痛苦。

他感觉喉咙中有种火烧火燎般的疼痛，就连吗啡都无法将之化解。

我在这里的事情已经做完了。

他激起了人们的敬畏之心，人们又有了希望。

在帕利恩凹室里的时候，教皇内侍遵从上帝的教诲，举行了涂油仪式。他的身体上，发须上，面颊上，麻布长袍上，全身都涂满了灯油。他这会儿像是浸泡在神圣的绿色灯油中一样，气味芬芳，如母亲的体香，可却易燃烧。他将会幸运地升天。那是个充满奇迹而又迅速的过程。他留给世人的不再是丑闻……而是一股新的力量和奇迹。

他的手滑入长袍的口袋，摸出从帕利恩凹室里拿来的小小的金色打火机。

他低声说出了上帝在最后审判时说过的一句话。

熊熊烈焰直冲云霄，上帝的天使也会在火焰中升天。

他的大拇指按在了打火机上。

人们还在圣彼得广场上唱着颂歌……

题目描述

给定 $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))$。

输入格式

第一行，两个数 $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
	}
}

输出格式

对于每个询问 $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

提示

对于 $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$。