Cho hai dãy số nguyên dương $a$ và $b$ có độ dài lần lượt là $n$ và $m$, hãy viết chương trình thực hiện các truy vấn sau. Tất cả các chỉ số đều bắt đầu từ 1.

• 1 y z: Thực hiện $a[y] = z$ và sau đó in ra $F(a, b)$. ($1 \le y \le n$, $1 \le z \le 10^5$)
• 2 y z: In ra $F(a[y..z], b)$. ($1 \le y \le z \le n$)
• 3 y z: In ra $f(b[y..m], b[z..m])$. ($1 \le y, z \le m$)
• 4 p q r s: Nếu dãy $[b_p, b_{p+1}, \ldots, b_q, b_r, b_{r+1}, \ldots, b_s]$ là một dãy con liên tiếp của $b$, thì in ra "yes", ngược lại in ra "no". ($1 \le p \le q \le m$, $1 \le r \le s \le m$)

$a[l..r]$ là dãy con $[a_l, a_{l+1}, \ldots, a_r]$. Định nghĩa tương tự cho $b$.

Với hai dãy $x, y$:

• $f(x, y)$ là độ dài của tiền tố chung dài nhất của $x$ và $y$.
• $F(x, y)$ là một cặp số nguyên $(p, q)$, trong đó $p$ là giá trị lớn nhất của $f(z, y)$ trên tất cả các hậu tố $z$ của $x$, và $q$ là số lượng $z$ đạt được giá trị lớn nhất này.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$, độ dài của $a$. ($1 \le n \le 10^5$)

Dòng tiếp theo chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$. ($1 \le a_i \le 10^5$)

Dòng tiếp theo chứa một số nguyên $m$, độ dài của $b$. ($1 \le m \le 10^5$)

Dòng tiếp theo chứa $m$ số nguyên $b_1, b_2, \ldots, b_m$. ($1 \le b_i \le 10^5$)

Dòng tiếp theo chứa một số nguyên $q$, số lượng truy vấn. ($1 \le q \le 10^5$)

$q$ dòng tiếp theo mỗi dòng chứa một truy vấn như mô tả ở trên.

Dữ liệu ra

Đối với mỗi truy vấn, in ra kết quả theo thứ tự, mỗi kết quả trên một dòng riêng.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

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