AT_joi2022_yo2_a.図書館 2 (Library 2)

喜欢读书的比太郎决定在图书馆借书阅读。由于比太郎的家很小，地板上只能放下一本书的空间。不过高度足够，因此比太郎决定把书一本一本地堆叠起来管理。

比太郎接下来会进行 $Q$ 次操作。第 $i$ 次（$1 \leq i \leq Q$）操作由字符串 $S_i$ 表示。$S_i$ 要么是由小写英文字母组成的字符串，要么是 READ，其含义如下：

• 如果 $S_i$ 是由小写英文字母组成的字符串，则比太郎会从图书馆借一本书名为 $S_i$ 的书，并将其堆放在最上面。
• 如果 $S_i$ 为 READ，则比太郎会阅读堆叠空间最上面的一本书，并将其归还给图书馆。

请你输出比太郎按照阅读顺序读过的书名。

给定 $Q$ 次操作的内容，请编写程序，按比太郎阅读书籍的顺序输出他读过的书名。

输入以以下格式从标准输入给出。

$Q$
$S_1$
$S_2$
$\vdots$
$S_Q$

对于每一次 $S_i$ 为 READ 的操作，按顺序每行输出比太郎读过的书名。

限制条件

• $2 \leq Q \leq 200\,000$。
• $Q$ 是整数。
• $S_i$ 是长度在 $1$ 到 $10$ 之间的字符串（$1 \leq i \leq Q$）。
• $S_i$ 要么是由小写英文字母组成的字符串，要么是 READ（$1 \leq i \leq Q$）。
• 至少存在一个 $i$ 使得 $S_i$ 为 READ。
• 当 $S_i$ 为 READ 时，堆叠空间中一定至少有一本书（$1 \leq i \leq Q$）。

子任务

1.（40 分）$Q \leq 2\,000$。
2.（60 分）无额外限制。

评测说明

所有提交将在评测系统上进行评分。

提交的源代码在对应子任务的所有测试数据上均输出正确结果时，该子任务判为正确。

每次提交的得分为所有判为正确的子任务分数之和。

本题的得分为所有提交中得分的最大值。

当前得分可在“提交结果”标签页的“我的得分情况”中查看。

样例解释 1

在此输入样例中，比太郎的操作如下：

1. 将书名为 joi 的书堆放到空间中。此时，空间中的书名为 joi。
2. 将书名为 joig 的书堆放到空间中。此时，空间中的书名从上到下依次为 joig、joi。
3. 将书名为 ioi 的书堆放到空间中。此时，空间中的书名从上到下依次为 ioi、joig、joi。
4. 读并归还最上面的 ioi。此时，空间中的书名从上到下依次为 joig、joi。
5. 将书名为 egoi 的书堆放到空间中。此时，空间中的书名从上到下依次为 egoi、joig、joi。
6. 读并归还最上面的 egoi。此时，空间中的书名从上到下依次为 joig、joi。
7. 读并归还最上面的 joig。此时，空间中的书名为 joi。

因此，比太郎读过的书名依次为 ioi、egoi、joig，每行输出一个。

该输入样例满足所有子任务的限制条件。

样例解释 2

该输入样例满足所有子任务的限制条件。

由 ChatGPT 4.1 翻译