可可想用 3 种不同种类的巧克力排成三角形来装饰房间的一面墙。具体方法如下：

• 首先，用任意的巧克力填满最底下一行。
• 从倒数第二行往上，每个位置的巧克力种类由其正下方的两个巧克力决定，规则如下：
  • 如果下方的两个巧克力种类相同，则在该位置放置相同种类的巧克力。（例如：两个白巧克力上方放置白巧克力。）
  • 如果下方的两个巧克力种类不同，则在该位置放置与这两个巧克力种类都不同的第三种巧克力。（例如：薄荷巧克力和白巧克力上方放置黑巧克力。）

下图是根据上述规则完成的巧克力装饰示例。

还没有决定最底下一行设计的可可，正在尝试逐个更换巧克力。请在可可每次更换一个巧克力时，告诉她最顶端将会是什么种类的巧克力。

输入格式

第一行包含一个整数 $N$，表示最底下一行的巧克力数量。($1 \le N \le 500\;000$)

第二行包含一个长度为 $N$ 的字符串，表示这 $N$ 个巧克力的种类。白巧克力用 W 表示，黑巧克力用 D 表示，薄荷巧克力用 M 表示。

第三行包含一个整数 $Q$，表示可可更换巧克力的次数。($1 \le Q \le 500\;000$)

接下来的 $Q$ 行，每行包含一个要更换的巧克力的位置 $i$ 和巧克力的种类 $c$。($1 \le i \le N$，$c$ 为 W、D、M 中的一个) 所有的修改都是累积的。

输出格式

第一行输出在初始状态下，最顶端的巧克力种类。

接下来的 $Q$ 行，每行输出在可可每次更换一个巧克力后，最顶端的巧克力种类。

样例

样例输入 1

9
WDMMDDWMM
5
1 M
4 D
8 W
7 M
5 M

样例输出 1

M
D
M
D
W
D