题目描述

有 $N$ 个方格从左到右排成一行，从左到右依次编号为方格 $1$ 到方格 $N$。颜色用英文小写字母表示。

初始时，每个方格的颜色都是 a，且每个方格上都没有放置任何东西。

给定 $Q$ 个询问，请按给定的顺序依次处理。每个询问是以下两种类型之一：

• 1 X：若方格 $X$ 上没有放置胶带，则在它上面放置一块胶带；若上面已经放置了胶带，则把胶带取走。
• 2 C：把所有没有放置胶带的方格的颜色改为 $C$。

请求出处理完所有询问后每个方格的颜色（无论该方格上是否放置了胶带）。

输入格式

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

• $N$ $Q$
• $\mathrm{query}_1$
• $\vdots$
• $\mathrm{query}_Q$

每个询问 $\mathrm{query}_i ~ (1 \le i \le Q)$ 以如下形式给出：

• 1 X

或者：

• 2 C

输出格式

把每个方格最终的颜色从左到右拼接成一个长度为 $N$ 的字符串，并输出该字符串。

3 5
1 2
2 b
1 1
1 2
2 c

bcc

对于胶带的状态，我们用从左到右依次拼接得到的字符串来表示：若方格上放置了胶带则为 #，否则为 .。

这些询问对方格颜色和胶带状态的改变如下。初始状态为 aaa 和 ...。

• 处理第 $1$ 个询问会在方格 $2$ 上放置一块胶带。状态变为 aaa 和 .#.。
• 处理第 $2$ 个询问会把没有放置胶带的方格的颜色改为 b。状态变为 bab 和 .#.。
• 处理第 $3$ 个询问会在方格 $1$ 上放置一块胶带。状态变为 bab 和 ##.。
• 处理第 $4$ 个询问会把方格 $2$ 上的胶带取走。状态变为 bab 和 #..。
• 处理第 $5$ 个询问会把没有放置胶带的方格的颜色改为 c。状态变为 bcc 和 #..。

因此输出 bcc。方格 $1$ 上仍然放置着胶带，但即使如此也要输出该方格的颜色。

10 15
1 8
2 m
1 3
1 10
2 q
1 6
1 10
2 d
1 1
2 z
1 9
2 f
1 4
1 7
2 k

dkmfkqfazk

数据范围

• $1 \le N,Q \le 3\times 10^5$

• 每个询问都是类型 $1$ 或类型 $2$。

• 在类型 $1$ 的询问中，$X$ 是满足 $1 \le X \le N$ 的整数。

• 在类型 $2$ 的询问中，$C$ 是单个英文小写字母。

• 来源：AtCoder ABC 477 D

子任务设置

• 子任务 1（30 分）：$N,Q \le 2000$。
• 子任务 2（70 分）：无特殊限制。