P11730 [集训队互测 2015] Sone2

Sone 有一只调皮的宠物 Jie。 某天，Sone 在研究串匹配问题。 在他出门的时候在桌子上放了两个字符串：一个长度为 $n$ 的字符串 $a$ 和一个长度为 $m$ 的字符串 $b$。设 $\Sigma$ 为字符串的字符集大小，即字符串中每个字符都是 $1$ 到 $\Sigma$ 之间的整数。 在走之前，Sone 严肃地警告 Jie：你不准动 $b$ 串，那个串很重要！ 于是，Jie 就只能调戏 $a$ 串。 设 $a[l:r]$ 表示 $a$ 串第 $l$ 个字符到第 $r$ 个字符之间的子串。特别地，当 $l>r$ 时，$a[l:r]$ 表示空串。 Jie 定义了一个关于 $s$ 串和 $t$ 串的函数： $$f(s,t)=\max_{s[1:k]=t[1:k]}k$$ 即 $s$ 和 $t$ 的最长公共前缀的长度。 Jie 又定义了一个关于 $a$ 串和 $b$ 串的函数 $F(a,b)$。$F(a,b)$ 的值是一个二元组 $(x,y)$，其中 $x$ 为： $$x=\max_{i=1}^{\lvert a \rvert} f(a[i:\lvert a \rvert],b)$$ 而 $y$ 表示满足 $f(a[i:\lvert a \rvert], b) = x$ 的 $i$ 的个数。 本来问题很简单的，但由于 Jie 太调皮了，一共有 $q$ 个时刻，每个时刻他会有四种行为： 1. 他会修改 $a$ 串的某一位，然后询问 $F(a,b)$。（操作后 $a$ 不会还原） 2. 他会选择 $a$ 串中的一个子串 $c$，询问 $F(c,b)$。 3. 他会选择 $b$ 串的两个后缀，并询问这两个后缀的最长公共前缀的长度。 4. 他会选择 $b$ 串的两个子串 $s_1,s_2$，并询问把 $s_1$ 和 $s_2$ 串联起来得到的字符串是否是 $b$ 串的子串，是的话输出 `yes`，否则输出 `no`（不含引号）。 于是，Jie 困扰了，希望聪明的你能解决这个问题。

设 $\Sigma$ 为字符串的字符集大小，即字符串中每个字符都是 $1$ 到 $\Sigma$ 之间的整数。 第一行一个整数表示测试点编号。（样例和 Extra Test 中测试点编号为 $0$ 到 $20$ 间的任意整数） 第二行一个正整数表示 $a$ 串的长度 $n$。 第三行 $n$ 个 $1$ 到 $\Sigma$ 间的整数表示 $a$ 串。 第四行一个正整数表示 $b$ 串的长度 $m$。 第五行 $m$ 个 $1$ 到 $\Sigma$ 间的整数表示 $b$ 串。 第六行一个正整数表示询问个数 $q$。 接下来 $q$ 行表示操作，每行包含若干个整数。第一个整数 $x$ 表示操作类型： 1. 若 $x=1$ 则后面有两个整数 $y,z$，表示把 $a$ 串中的第 $y$ 位改成 $z$。$1 \leq y \leq n$，$1 \leq z \leq \Sigma$。 2. 若 $x=2$ 则后面有两个整数 $y,z$，表示询问的子串在 $a$ 串中的区间 $[y, z]$。$1 \leq y \leq z \leq n$。 3. 若 $x=3$ 则后面有两个整数 $y,z$，表示询问的两个后缀的第一个字符在 $b$ 串中的位置。$1 \leq y, z \leq m$。 4. 若 $x=4$ 则后面有四个整数 $l_1,r_1,l_2,r_2$，表示询问的两个子串在 $b$ 串中的区间 $[l_1,r_1]$ 和 $[l_2,r_2]$。$1 \leq l_1 \leq r_1 \leq m$，$1 \leq l_2 \leq r_2 \leq m$。

有 $q$ 行，每行对应每种操作的答案。

| 测试点编号 | $n$ | $m$ | $q$ | $\Sigma$ | 备注 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1,2$ | $=10^3$ | $\leq 100$ | $=1000$ | $\leq 10^5$ | 无 | | $3,4$ | $=10^5$ | $\leq 100$ | $=10^5$ | $\leq 10^5$ | 无操作二 | | $5,6$ | $=10^5$ | $\leq 30$ | $=10^5$ | $\leq 10^5$ | 无 | | $7,8$ | $=10^5$ | $\leq 10^5$| $=10^5$ | $\leq 10^5$ | 只有操作三 | | $9,10$ | $=10^5$ | $\leq 10^5$ | $=10^5$ | $\leq 10^5$ | 只有操作四 | | $11\sim 16$ | $=10^5$ | $\leq 10^5$ | $=10^5$ | $\leq 5$ | $b$ 串的生成方式是：人工确定每种字符出现的比例，然后均匀随机选取一个满足这一比例的字符串作为 $b$ | | $17\sim 20$ | $=10^5$ | $\leq 10^5$ | $=10^5$ | $\leq 10^5$ | 无 |