Поликарп — большой любитель проводить время в соцсетях. Страница со списком чатов в его любимой соцсети устроена так, что при отсылке сообщения собеседнику чат с ним поднимается на самый верх страницы. Относительный порядок всех остальных чатов при этом не изменяется. Если ранее чата с этим собеседником не было, то просто в верх списка чатов вставляется новый чат.

Считая, что изначально список чатов пуст, по последовательности сообщений Поликарпа постройте список чатов после обработки всех его сообщений. Считайте, что никто из собеседников ничего Поликарпу не писал.