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 翻译