Даны две последовательности целых положительных чисел $a$ и $b$ длин $n$ и $m$ соответственно. Напишите программу, выполняющую следующие запросы. Все индексы начинаются с 1.

• 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$.
• $F(x, y)$ — это пара целых чисел $(p, q)$, где $p$ — максимальное значение $f(z, y)$ по всем суффиксам $z$ последовательности $x$, а $q$ — количество $z$, достигающих этого максимума.

Входные данные

Первая строка содержит целое число $n$ — длину $a$. ($1 \le n \le 10^5$)

Следующая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$. ($1 \le a_i \le 10^5$)

Следующая строка содержит целое число $m$ — длину $b$. ($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

Выходные данные 1

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