Étant donné deux séquences d'entiers positifs $a$ et $b$ de longueurs respectives $n$ et $m$, écrire un programme pour effectuer les requêtes suivantes. Tous les indices commencent à 1.

• 1 y z : Effectuer $a[y] = z$ puis afficher $F(a, b)$. ($1 \le y \le n$, $1 \le z \le 10^5$)
• 2 y z : Afficher $F(a[y..z], b)$. ($1 \le y \le z \le n$)
• 3 y z : Afficher $f(b[y..m], b[z..m])$. ($1 \le y, z \le m$)
• 4 p q r s : Si la séquence $[b_p, b_{p+1}, \ldots, b_q, b_r, b_{r+1}, \ldots, b_s]$ est une sous-séquence contiguë de $b$, alors afficher "yes", sinon afficher "no". ($1 \le p \le q \le m$, $1 \le r \le s \le m$)

$a[l..r]$ est la sous-séquence $[a_l, a_{l+1}, \ldots, a_r]$. Une définition similaire vaut pour $b$.

Pour deux séquences $x, y$ :

• $f(x, y)$ désigne la longueur du plus long préfixe commun de $x$ et $y$.
• $F(x, y)$ est une paire d'entiers $(p, q)$, où $p$ est la valeur maximale de $f(z, y)$ parmi tous les suffixes $z$ de $x$, et $q$ est le nombre de $z$ qui atteignent ce maximum.

Entrée

La première ligne contient un entier $n$, la longueur de $a$. ($1 \le n \le 10^5$)

La ligne suivante contient $n$ entiers $a_1, a_2, \ldots, a_n$. ($1 \le a_i \le 10^5$)

La ligne suivante contient un entier $m$, la longueur de $b$. ($1 \le m \le 10^5$)

La ligne suivante contient $m$ entiers $b_1, b_2, \ldots, b_m$. ($1 \le b_i \le 10^5$)

La ligne suivante contient un entier $q$, le nombre de requêtes. ($1 \le q \le 10^5$)

Les $q$ lignes suivantes contiennent chacune une requête comme décrit ci-dessus.

Sortie

Pour chaque requête, afficher le résultat dans l'ordre, chacun sur sa propre ligne.

Exemples

Entrée 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

Sortie 1

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