给定两个长度分别为 $n$ 和 $m$ 的正整数序列 $a$ 和 $b$，请编写一个程序执行以下查询。所有下标均从 1 开始。

• 1 y z: 执行 $a[y] = z$ 后输出 $F(a, b)$。($1 \le y \le n$, $1 \le z \le 10^5$)
• 2 y z: 输出 $F(a[y..z], b)$。($1 \le y \le z \le n$)
• 3 y z: 输出 $f(b[y..m], b[z..m])$。($1 \le y, z \le m$)
• 4 p q r s: 如果序列 $[b_p, b_{p+1}, \ldots, b_q, b_r, b_{r+1}, \ldots, b_s]$ 是 $b$ 的一个连续子序列，则输出 "yes"，否则输出 "no"。($1 \le p \le q \le m$, $1 \le r \le s \le m$)

$a[l..r]$ 是子序列 $[a_l, a_{l+1}, \ldots, a_r]$。对于 $b$ 有类似定义。

对于两个序列 $x, y$：

• $f(x, y)$ 表示 $x$ 和 $y$ 的最长公共前缀的长度。
• $F(x, y)$ 是一个整数对 $(p, q)$，其中 $p$ 是所有 $x$ 的后缀 $z$ 中 $f(z, y)$ 的最大值，$q$ 是达到该最大值的 $z$ 的个数。

输入格式

第一行包含一个整数 $n$，表示 $a$ 的长度。($1 \le n \le 10^5$)

接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$。($1 \le a_i \le 10^5$)

接下来一行包含一个整数 $m$，表示 $b$ 的长度。($1 \le m \le 10^5$)

接下来一行包含 $m$ 个整数 $b_1, b_2, \ldots, b_m$。($1 \le b_i \le 10^5$)

接下来一行包含一个整数 $q$，表示查询的个数。($1 \le q \le 10^5$)

接下来 $q$ 行，每行包含一个如上所述的查询。

输出格式

对于每个查询，按顺序输出结果，每个结果占一行。

样例

样例输入 1

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

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