Поликарп — большой любитель проводить время в соцсетях. Страница со списком чатов в его любимой соцсети устроена так, что при отсылке сообщения собеседнику чат с ним поднимается на самый верх страницы. Относительный порядок всех остальных чатов при этом не изменяется. Если ранее чата с этим собеседником не было, то просто в верх списка чатов вставляется новый чат.
Считая, что изначально список чатов пуст, по последовательности сообщений Поликарпа постройте список чатов после обработки всех его сообщений. Считайте, что никто из собеседников ничего Поликарпу не писал.
В первой строке записано целое число n (1 ≤ n ≤ 200 000) — количество сообщений Поликарпа. Далее в n строках перечислены адресаты сообщений в порядке отсылки сообщений. Имя каждого адресата — непустая последовательность строчных букв английского алфавита длины не более 10.
Выведите всех адресатов, с кем общался Поликарп, в порядке расположения чатов с ними сверху вниз.
В первом тестовом примере Поликарп сначала напишет пользователю с именем «alex», и список примет вид:
Затем Поликарп напишет пользователю с именем «ivan» и список чатов будет выглядеть следующим образом:
Третье сообщение Поликарп напишет пользователю с именем «roman». После этого список чатов будет выглядеть следующим образом:
Четвёртое сообщение Поликарп напишет пользователю с именем «ivan», которому он уже отправлял сообщение, поэтому список чатов изменится следующим образом:
4 alex ivan roman ivan
ivan roman alex
8 alina maria ekaterina darya darya ekaterina maria alina
alina maria ekaterina darya
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач