Sequence and Queries 34

You are given two sequences $a$ and $b$ of positive integers with lengths $n$ and $m$. Write a program that processes the queries below. All indices are 1-based.

• 1 y z: set $a[y] = z$, then print $F(a, b)$. ($1 \le y \le n$, $1 \le z \le 10^5$)
• 2 y z: print $F(a[y..z], b)$. ($1 \le y \le z \le n$)
• 3 y z: print $f(b[y..m], b[z..m])$. ($1 \le y, z \le m$)
• 4 p q r s: print yes if the sequence $[b_p, b_{p+1}, \ldots, b_q, b_r, b_{r+1}, \ldots, b_s]$ is a contiguous subsequence of $b$, and no otherwise. ($1 \le p \le q \le m$, $1 \le r \le s \le m$)

$a[l..r]$ is the subsequence $[a_l, a_{l+1}, \ldots, a_r]$. The same definition applies to $b$.

For two sequences $x$ and $y$:

• $f(x, y)$ is the length of the longest common prefix of $x$ and $y$.
• $F(x, y)$ is the pair of integers $(p, q)$, where $p$ is the maximum of $f(z, y)$ over all suffixes $z$ of $x$, and $q$ is the number of suffixes $z$ that attain this maximum.

The first line gives the length $n$ of $a$. ($1 \le n \le 10^5$)

The next line gives $n$ integers $a_1, a_2, \ldots, a_n$. ($1 \le a_i \le 10^5$)

The next line gives the length $m$ of $b$. ($1 \le m \le 10^5$)

The next line gives $m$ integers $b_1, b_2, \ldots, b_m$. ($1 \le b_i \le 10^5$)

The next line gives the number of queries $q$. ($1 \le q \le 10^5$)

Each of the following $q$ lines contains a query as described above.

Print the result of each query in order, one per line.