Problem Statement

You are given a string $S$ of length $N$ consisting of A and B. Process a total of $Q$ queries of the following types.

1 i c

Type $1$: Change the $i$-th character of $S$ to $c$.

2 l r

Type $2$: Let string $T$ be the string obtained by extracting the $l$-th through $r$-th characters of the current string $S$. If it is possible to obtain string $T$ by the following operation, output Yes; otherwise, output No.

• Starting from the empty string, perform the following two operations any number of times, possibly zero, in any order.
  • Choose any position in the string (possibly the beginning or the end) and insert A there.
  • Choose any position in the string (possibly the beginning or the end) and insert AB there.

Constraints

• $N$ is an integer satisfying $1 \le N \le 5 \times 10^5$.
• $S$ is a string of length $N$ consisting of A and B.
• $Q$ is an integer satisfying $1 \le Q \le 2 \times 10^5$.
• Each given query is of type $1$ or $2$.
• Queries of type $1$ satisfy the following constraints:
  • $i$ is an integer satisfying $1 \le i \le N$, and
  • $c$ is A or B.
• Queries of type $2$ satisfy the following constraints:
  • $l$ and $r$ are integers satisfying $1 \le l \le r \le N$.

Input

The input is given from Standard Input in the following format:

• $N$
• $S$
• $Q$
• ${\rm Query}_1$
• ${\rm Query}_2$
• $\vdots$
• ${\rm Query}_Q$

Here, ${\rm Query}_i$ represents the $i$-th query, and the input format for a query follows the format described in the problem statement.

Output

Each time a query of type $2$ is given, output the answer on one line.

10
AABBAABABB
6
2 1 10
1 5 B
2 1 10
2 6 8
1 3 A
2 1 10

Yes
No
Yes
Yes

This input contains six queries.

• Initially, $S=$ AABBAABABB.

• For the $1$-st query, $T=$ AABBAABABB, obtained by extracting the $1$-st through $10$-th characters of $S$, can be obtained by the following steps, so output Yes.

• Start from the empty string.

• Insert AB at the beginning of the empty string, making the string AB.

• Insert AB right after the $1$-st character of AB, making the string AABB.

• Insert AB at the end of AABB, making the string AABBAB.

• Insert AB right after the $5$-th character of AABBAB, making the string AABBAABB.

• Insert AB right after the $7$-th character of AABBAABB, making the string AABBAABABB.

• For the $2$-nd query, change the $5$-th character of $S$ to B. As a result, $S=$ AABBBABABB.

• For the $3$-rd query, $T=$ AABBBABABB, obtained by extracting the $1$-st through $10$-th characters of $S$, cannot be obtained by the operation described in the problem statement, so output No.

• For the $4$-th query, $T=$ ABA, obtained by extracting the $6$-th through $8$-th characters of $S$, can be obtained by the operation described in the problem statement, so output Yes.

• For the $5$-th query, change the $3$-rd character of $S$ to A. As a result, $S=$ AAABBABABB.

• For the $6$-th query, $T=$ AAABBABABB, obtained by extracting the $1$-st through $10$-th characters of $S$, can be obtained by the operation described in the problem statement, so output Yes.

• Source: AtCoder ABC 473 F