수열과 쿼리 34

시간 제한2초메모리 제한512 MB

요약

두 정수 수열 a와 b를 두고 갱신과 구간 질의를 처리한다. a의 접미사 중 b와 가장 길게 일치하는 것의 길이와 그 개수를 구하고, b의 두 접미사의 최장 공통 접두사를 구하며, b의 두 부분 문자열을 이어 붙인 것이 b의 연속 부분 문자열인지 판정한다.

문제

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

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

예제 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

예상 출력