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$ 行，每行对应每种操作的答案。

0
10
1 2 3 3 3 1 2 3 2 1
3
1 3 1
10
3 1 3
4 3 3 2 2
2 2 10
1 3 2
2 7 9
2 7 10
2 3 9
2 2 8
1 7 1
1 4 2

1
yes
1 2
1 3
0 3
1 1
1 1
1 1
2 1
2 1

限制与约定

时间限制：$2\texttt{s}$

空间限制：$256\texttt{MB}$

来源

中国国家集训队互测2015 - By 王鉴浩

下载

样例数据下载