Поликарп — большой любитель проводить время в соцсетях. Страница со списком чатов в его любимой соцсети устроена так, что при отсылке сообщения собеседнику чат с ним поднимается на самый верх страницы. Относительный порядок всех остальных чатов при этом не изменяется. Если ранее чата с этим собеседником не было, то просто в верх списка чатов вставляется новый чат.
Считая, что изначально список чатов пуст, по последовательности сообщений Поликарпа постройте список чатов после обработки всех его сообщений. Считайте, что никто из собеседников ничего Поликарпу не писал.
Выходные данные
Выведите всех адресатов, с кем общался Поликарп, в порядке расположения чатов с ними сверху вниз.
Примечание
В первом тестовом примере Поликарп сначала напишет пользователю с именем «alex», и список примет вид:
- alex
Затем Поликарп напишет пользователю с именем «ivan» и список чатов будет выглядеть следующим образом:
- ivan
- alex
Третье сообщение Поликарп напишет пользователю с именем «roman». После этого список чатов будет выглядеть следующим образом:
- roman
- ivan
- alex
Четвёртое сообщение Поликарп напишет пользователю с именем «ivan», которому он уже отправлял сообщение, поэтому список чатов изменится следующим образом:
- ivan
- roman
- alex
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
alex
ivan
roman
ivan
|
ivan
roman
alex
|
|
2
|
8
alina
maria
ekaterina
darya
darya
ekaterina
maria
alina
|
alina
maria
ekaterina
darya
|