Given two strings $a$ and $b$, support the following four operations:

1. Set the $y$th character of $a$ to $z$ and then output $F(a,b)$.

2. Consider the 1-indexed substring of $a$ starting at index $y$ ending at index $z$, call it $s$. Print $F(s,b)$.

3. Consider the suffixes of $b$ starting with the $y$th and $z$th indexed characters, call them $t$ and $u$. Print $f(t,u)$.

4. Consider the 1-indexed substrings of $b$ starting and ending at $l_1$ and $r_1$, and $l_2$ and $r_2$. Determine if their concatenation is a substring of $b$. Print yes if so, print no otherwise.

$f(x,y)$ is the length of the longest common prefix of $x$ and $y$.

$F(x,y)$ is a pair $(p,q)$ where $p$ is the maximum value of $f(z,y)$ where $z$ varies over all suffixes of $x$, and $q$ is the number of suffixes that yield that maximum value.

Constraints

$N,M,Q\le {10}^5$

Each character in the string will be a positive integer no larger than ${10}^5$.

Input

The first line contains a single integer, the test case number. You may ignore this line.

The next line contains a single positive integer, $N$, representing the length of $a$.

The next line contains $N$ space-separated integers, the string $a$.

The next line contains a single positive integer, $M$, representing the length of $b$.

The next line contains $M$ space-separated integers, the string $b$.

The next line contains a single positive integer, $Q$, representing the number of operations.

The next $Q$ lines indicate the operations to be performed in order.

If the operation is the first one, there will be three space-separated integers, $1$, $y$, and $z$.

If the operation is the second one, there will be three space-separated integers, $2$, $y$, and $z$.

If the operation is the third one, there will be three space-separated integers, $3$, $y$, and $z$.

If the operation is the fourth one, there will be five space-separated integers, $4$, $l_1$, $r_1$, $l_2$, and $r_2$.

Output

Print an answer for each operation. All answers go on their own lines.

Sample Input

0
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

Sample Output

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