수열과 쿼리 34 - 問題

길이가 각각 $n, m$이며 양의 정수로 이루어진 두 수열 $a, b$가 주어질 때, 아래의 쿼리를 수행하는 프로그램을 작성하시오. 모든 인덱스는 1-based 이다.

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$의 최대 공통 접두사 (Longest common prefix) 의 길이이다.
$F(x, y)$ 는 두 정수의 쌍 $(p, q)$로, $p$는 모든 $x$의 접미사 (suffix) $z$에 대해 $f(z, y)$ 의 최댓값, $q$는 그러한 최댓값을 이루는 $z$의 개수를 뜻한다.

입력

첫 번째 줄에 $a$의 길이 $n$이 주어진다. ($1 \le n \le 10^5$)

다음 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$ 이 주어진다. ($1 \le a_i \le 10^5$)

다음 줄에 $b$의 길이 $m$이 주어진다. ($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$개의 줄에 위에서 설명한 것과 같은 쿼리가 주어진다.

각각의 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

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