Dadas dos secuencias de enteros positivos $a$ y $b$ de longitudes $n$ y $m$ respectivamente, escriba un programa para realizar las siguientes consultas. Todos los índices comienzan en 1.

• 1 y z: Realice $a[y] = z$ y luego muestre $F(a, b)$. ($1 \le y \le n$, $1 \le z \le 10^5$)
• 2 y z: Muestre $F(a[y..z], b)$. ($1 \le y \le z \le n$)
• 3 y z: Muestre $f(b[y..m], b[z..m])$. ($1 \le y, z \le m$)
• 4 p q r s: Si la secuencia $[b_p, b_{p+1}, \ldots, b_q, b_r, b_{r+1}, \ldots, b_s]$ es una subsecuencia contigua de $b$, entonces muestre "yes", en caso contrario muestre "no". ($1 \le p \le q \le m$, $1 \le r \le s \le m$)

$a[l..r]$ es la subsecuencia $[a_l, a_{l+1}, \ldots, a_r]$. Una definición similar se cumple para $b$.

Para dos secuencias $x, y$:

• $f(x, y)$ denota la longitud del prefijo común más largo de $x$ e $y$.
• $F(x, y)$ es un par de enteros $(p, q)$, donde $p$ es el valor máximo de $f(z, y)$ sobre todos los sufijos $z$ de $x$, y $q$ es el número de $z$ que alcanzan este máximo.

Restricciones

• $1 \le n \le 10^5$
• $1 \le a_i \le 10^5$
• $1 \le m \le 10^5$
• $1 \le b_i \le 10^5$
• $1 \le q \le 10^5$
• Para cada consulta de tipo 1: $1 \le y \le n$, $1 \le z \le 10^5$
• Para cada consulta de tipo 2: $1 \le y \le z \le n$
• Para cada consulta de tipo 3: $1 \le y, z \le m$
• Para cada consulta de tipo 4: $1 \le p \le q \le m$, $1 \le r \le s \le m$

Entrada

La primera línea contiene un entero $n$, la longitud de $a$. ($1 \le n \le 10^5$)

La siguiente línea contiene $n$ enteros $a_1, a_2, \ldots, a_n$. ($1 \le a_i \le 10^5$)

La siguiente línea contiene un entero $m$, la longitud de $b$. ($1 \le m \le 10^5$)

La siguiente línea contiene $m$ enteros $b_1, b_2, \ldots, b_m$. ($1 \le b_i \le 10^5$)

La siguiente línea contiene un entero $q$, el número de consultas. ($1 \le q \le 10^5$)

Las siguientes $q$ líneas contienen cada una una consulta como se describe anteriormente.

Salida

Para cada consulta, muestre el resultado en orden, cada uno en su propia línea.

Ejemplos

Entrada 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

Salida 1

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