← 返回题目列表

Codeforces · 637/B

B. 聊天顺序

中文机器翻译题面 查看原题

Polycarp 非常喜欢在社交网络中消磨时间。在他最喜欢的网络中创建一个带有聊天列表的页面,这样当消息发送给某个朋友时,他朋友的聊天就会上升到页面的最顶部。其他聊天的相对顺序不会改变。如果之前没有与该朋友聊天,则新的聊天会简单地插入到列表顶部。

假设聊天列表最初是空的,根据 Polycaprus 消息的顺序,在处理完所有消息后创建一个聊天列表。假设没有朋友给波利卡普斯写过任何消息。

输入

第一行包含整数 n (1 ≤ n ≤ 200 000) — Polycarpus 的消息数。接下来的 n 行按照消息发送的顺序列出消息收件人。每个参与者的名字是一个非空的小写英文字母序列,长度最多为10个。

输出

按照与 Polycarp 聊天的顺序从上到下打印所有与其交谈过的收件人。

示例

输入 #1

4
alex
ivan
roman
ivan

输出 #1

ivan
roman
alex

输入 #2

8
alina
maria
ekaterina
darya
darya
ekaterina
maria
alina

输出 #2

alina
maria
ekaterina
darya

注意

在第一个测试用例中,Polycarpus 首先向名为“alex”的朋友写信,列表如下所示:

1.亚历克斯

然后 Polycarpus 写信给名为“ivan”的朋友,列表如下:

1.伊万
2.亚历克斯

Polycarpus 向名为“roman”的朋友写入第三条消息,列表如下:

1.罗马
2.伊万
3.亚历克斯

Polycarpus 将第四条消息写入名为“ivan”的朋友,他已经向该朋友发送了消息,因此聊天列表发生如下变化:

1.伊万
2.罗马
3.亚历克斯