题目描述

在黑猫警长的世界里，螳螂姑娘新婚之夜遵循物种的古老传统：每当一只螳螂与伴侣结合，总有一方会被吃掉。于是，婚宴上的螳螂们发生了奇特的“右移弑夫”现象。

我们把婚宴大厅抽象为一排 $N$ 个格子（从左到右），每个格子中可能有 0 或 1 只螳螂。

当有新的螳螂进入第 $i$ 个格子时：

• 若该格子原本为空，则它安然留下；
• 若该格子原本已有一只螳螂，则它们会展开宿命的婚宴：其中一只被吃掉，另一只走向右边的下一个格子；
• 这个“右移”过程可能会层层触发，直到某只螳螂找到空格留下，或者走出了最右边离开了婚宴大厅，真的很久！

在婚宴进行的过程中，黑猫警长需要时刻观察某个格子里究竟有没有螳螂。

输入格式

第一行两个整数 $N, Q$。

第二行一个长度为 $N$ 的 01 串，表示初始每个格子的状态（1 表示有螳螂，0 表示空）。其中第一个字符表示最左格，第 $N$ 个字符表示最右格。

接下来 $Q$ 行，每行一个操作：

• A i：往第 $i$ 个格子放入一只新的螳螂，并按照上述规则触发“右移弑夫”。
• Q i：询问当前第 $i$ 个格子中是否有螳螂（输出 0 或 1）。

输出格式

对于每个 Q 操作，输出一行答案 0 或 1。

5 6
01011
A 5
Q 5
A 3
A 1
A 1
Q 5

0
1

数据范围

数据满足 $1 \le i \leq N, 1 \le N, Q \le 2 \times 10^5$。