题目描述

给定一个由 A 和 B 组成的长度为 $N$ 的字符串 $S$。 请处理共 $Q$ 个以下类型的询问。

1 i c

类型 $1$：将 $S$ 的第 $i$ 个字符改为 $c$。

2 l r

类型 $2$： 设字符串 $T$ 为从当前字符串 $S$ 中取出第 $l$ 个到第 $r$ 个字符所得到的字符串。 如果能够通过以下操作得到字符串 $T$，输出 Yes；否则输出 No。

• 从空字符串开始，以任意顺序进行以下两种操作任意多次（可以是零次）。
  • 选择字符串中的任意一个位置（可以是开头或结尾），在该处插入 A。
  • 选择字符串中的任意一个位置（可以是开头或结尾），在该处插入 AB。

输入格式

输入按以下格式从标准输入读入：

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

其中，${\rm Query}_i$ 表示第 $i$ 个询问，每个询问的输入格式遵循题目描述中给出的格式。

输出格式

每当给出一个类型 $2$ 的询问时，将答案输出为一行。

数据范围

• $N$ 是满足 $1 \le N \le 5 \times 10^5$ 的整数。
• $S$ 是由 A 和 B 组成的长度为 $N$ 的字符串。
• $Q$ 是满足 $1 \le Q \le 2 \times 10^5$ 的整数。
• 每个给定的询问为类型 $1$ 或类型 $2$。
• 类型 $1$ 的询问满足以下限制：
  • $i$ 是满足 $1 \le i \le N$ 的整数；
  • $c$ 为 A 或 B。
• 类型 $2$ 的询问满足以下限制：
  • $l$ 和 $r$ 是满足 $1 \le l \le r \le N$ 的整数。

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

该输入包含六个询问。

• 初始时，$S=$ AABBAABABB。

• 对于第 $1$ 个询问，$T=$ AABBAABABB，即取出 $S$ 的第 $1$ 到第 $10$ 个字符得到的字符串，可以通过以下步骤得到，因此输出 Yes。

• 从空字符串开始。

• 在空字符串的开头插入 AB，字符串变为 AB。

• 在 AB 的第 $1$ 个字符之后插入 AB，字符串变为 AABB。

• 在 AABB 的末尾插入 AB，字符串变为 AABBAB。

• 在 AABBAB 的第 $5$ 个字符之后插入 AB，字符串变为 AABBAABB。

• 在 AABBAABB 的第 $7$ 个字符之后插入 AB，字符串变为 AABBAABABB。

• 对于第 $2$ 个询问，将 $S$ 的第 $5$ 个字符改为 B。此后 $S=$ AABBBABABB。

• 对于第 $3$ 个询问，$T=$ AABBBABABB，即取出 $S$ 的第 $1$ 到第 $10$ 个字符得到的字符串，无法通过题目描述中的操作得到，因此输出 No。

• 对于第 $4$ 个询问，$T=$ ABA，即取出 $S$ 的第 $6$ 到第 $8$ 个字符得到的字符串，可以通过题目描述中的操作得到，因此输出 Yes。

• 对于第 $5$ 个询问，将 $S$ 的第 $3$ 个字符改为 A。此后 $S=$ AAABBABABB。

• 对于第 $6$ 个询问，$T=$ AAABBABABB，即取出 $S$ 的第 $1$ 到第 $10$ 个字符得到的字符串，可以通过题目描述中的操作得到，因此输出 Yes。

• 来源：AtCoder ABC 473 F

子任务设置

• 子任务 1（30 分）：$N \le 2000$ 且 $Q \le 2000$。
• 子任务 2（30 分）：没有类型 $1$ 的询问（字符串不会被修改）。
• 子任务 3（40 分）：无特殊限制。