You have $N$ tiles numbered from tile $1$ to tile $N$.
Each tile has a color on its front side and a color on its back side, each of which is either black or white. Here, black is represented by the character B, and white is represented by the character W.

For tile $i$ $(1 \le i \le N)$, the color of its front side is given by the $i$-th character of the string $S$.
For tile $i$ $(1 \le i \le N)$, the color of its back side is given by the $i$-th character of the string $T$.

Uzbekistan is famous for its historical architecture decorated with tiles. After visiting mosques and madrasas in Uzbekistan and being fascinated by their beauty, you purchased a strange machine related to tiles.

This machine has a left platform and a right platform. By placing one tile on each platform, you can exchange the two tiles for a new single tile.

Let the tile placed on the left platform be $a$, and the tile placed on the right platform be $b$. The new tile $c$ obtained in exchange for tiles $a$ and $b$ satisfies the following conditions:

• The front color of $c$ is black if the back color of $a$ and the front color of $b$ are the same; otherwise, it is white.
• The back color of $c$ is black if the front color of $a$ and the back color of $b$ are the same; otherwise, it is white.

Using the $N$ tiles and the strange machine, you will perform actions over $Q$ days.
On day $j$ $(1 \le j \le Q)$, you perform either Pattern 1 or Pattern 2:

• Pattern 1: Change the front color of tile $X_j$ to the color represented by the character $Y_j$, and change the back color of tile $X_j$ to the color represented by the character $Z_j$. Here, $Y_j$ and $Z_j$ are either B or W.
• Pattern 2: Arrange tiles $L_j, L_j + 1, \dots, R_j$ in this order from left to right in a row. Then, by performing the following operation between $0$ and $R_j - L_j$ times (inclusive), determine whether it is possible to make the number of tiles whose front side is white exactly $M_j$.
  • Choose two adjacent tiles in the row and remove them from the row. Let the left tile among the two be placed on the left platform of the machine, and the right tile be placed on the right platform. Receive a new tile in exchange, and insert this new tile into the position where the two tiles originally were.

Given the initial tile information and the actions, write a program that outputs the result of each Pattern 2 action.

Input

The input is given from standard input in the following format:

N
S
T
Q
(Query 1)
(Query 2)
⋮
(Query Q)

Each $(\text{Query } j)$ $(1 \le j \le Q)$ consists of several integers and characters separated by spaces.
The first value is an integer $1$ or $2$, denoted by $P_j$.

• If $P_j = 1$, the line contains an integer $X_j$ and two characters $Y_j, Z_j$ in this order.
  This represents a Pattern 1 action: change the front color of tile $X_j$ to $Y_j$ and the back color to $Z_j$.
• If $P_j = 2$, the line contains three integers $L_j, R_j, M_j$ in this order.
  This represents a Pattern 2 action: arrange tiles $L_j, L_j + 1, \dots, R_j$ from left to right and determine whether it is possible, using the allowed operations, to make the number of tiles whose front side is white exactly $M_j$.

Output

For each $j$ such that $P_j = 2$ $(1 \le j \le Q)$, output Yes if it is possible to make the number of tiles whose front side is white exactly $M_j$, and No otherwise.

Print the answers in ascending order of $j$, each on a separate line.

Constraints

• $1 \le N \le 300\,000$.
• $S$ is a string of length $N$ consisting of B and W.
• $T$ is a string of length $N$ consisting of B and W.
• $1 \le Q \le 300\,000$.
• $P_j$ is either $1$ or $2$ $(1 \le j \le Q)$.
• If $P_j = 1$, then $1 \le X_j \le N$.
• If $P_j = 1$, then $Y_j$ is either B or W.
• If $P_j = 1$, then $Z_j$ is either B or W.
• If $P_j = 2$, then $1 \le L_j \le R_j \le N$.
• If $P_j = 2$, then $0 \le M_j \le R_j - L_j + 1$.
• $N, Q, P_j, X_j, L_j, R_j, M_j$ are all integers.

Scoring

1. (6 points) $N \le 6$.
2. (10 points) $N \le 100$, and $P_j = 2$ for all $j$.
3. (9 points) $N \le 500$, and $P_j = 2$ for all $j$.
4. (8 points) $N \le 1\,700$, and $P_j = 2$ for all $j$.
5. (23 points) $N \le 10\,000$, $Q \le 10\,000$.
6. (14 points) $N \le 100\,000$, $Q \le 100\,000$.
7. (30 points) No additional constraints.

Example

Input Example 1

4
WBWB
BWBB
5
2 3 4 1
2 1 2 0
1 3 B B
2 3 4 2
2 2 4 1

Output Example 1

Yes
Yes
No
Yes

On day 1, arrange tiles $3, 4$ from left to right.
If no operation is performed, only tile $3$ has a white front side, so it is possible to make the number of white-front tiles exactly $1$. Therefore, output Yes.

On day 2, arrange tiles $1, 2$ from left to right.
If we choose tiles $1$ and $2$ and perform one operation, the resulting row contains one tile whose front and back sides are both black. Thus, it is possible to make the number of white-front tiles exactly $0$. Therefore, output Yes.

On day 3, change both the front and back colors of tile $3$ to black.

On day 4, arrange tiles $3, 4$ from left to right.
It can be proven that it is impossible to make the number of white-front tiles exactly $2$. Therefore, output No.

On day 5, arrange tiles $2, 3, 4$ from left to right.
If we choose tiles $3$ and $4$ and perform one operation, the resulting row contains two tiles. The left tile is tile $2$, and the right tile has both front and back sides black.
If we then choose these two tiles and perform another operation, the resulting row contains one tile whose front side is white and back side is black. Thus, it is possible to make the number of white-front tiles exactly $1$. Therefore, output Yes.

This input example satisfies the constraints of Subtasks 1, 5, 6, and 7.

Input Example 2

6
BWBWWB
WBWBBB
8
2 1 3 2
2 2 6 0
2 1 5 3
2 3 3 0
2 3 4 1
2 5 6 2
2 2 6 4
2 1 4 2

Output Example 2

No
Yes
Yes
Yes
Yes
No
No
Yes

This input example satisfies the constraints of all subtasks.