H. Hierarchy
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В новом офисе Галактического Министерства Бюрократии установлена сложная система иерархии. Всего в офисе 109 отделов, пронумерованных последовательными целыми числами от 1 до 109.

Первоначально все отделы нового офиса пусты. После чего происходят события одного из следующих двух типов:

  1. Прибытие: в какой-то отдел переводится сотрудник из старого офиса. Для этого сотрудника известно его имя и дата рождения. При этом сотрудник получает локальный идентификатор k, если данное прибытие является k-м для данного отдела.
  2. Убытие: cотрудник из какого-то отдела, имеющий локальный идентификатор k, переводится в старый офис.

Руководитель каждого отдела определяется автоматически следующим образом:

  • Если какой-то сотрудник строго старше, чем остальные сотрудники, которые в настоящий момент зачислены в отдел, он становится руководителем отдела.
  • Если старшими являются несколько сотрудников отдела, родившиеся в один день, то руководителем отдела становится тот, у кого локальный идентификатор меньше.

Руководитель всего офиса также определяется автоматически следующим образом:

  • Если какой-то сотрудник строго старше остальных сотрудников, которые в данный момент работают в новом офисе, то этот сотрудник становится руководителем офиса.
  • Если существует несколько старейших сотрудников, то руководителем офиса становится тот из них, который работает в отделе с меньшим номером.
  • Если предыдущее правило не позволило однозначно определить руководителя, то руководителем становится тот сотрудник, у которого локальный идентификатор меньше.

При этом кадровая политика Министерства не допускает перевод одного и того же сотрудника в новый офис дважды.

Вам поручено написать программу, которая после каждого события выводит имя руководителя всего офиса и имя руководителя отдела, к которому относится данное событие.

Входные данные

Первая строка входа содержит одно целое число n — количество событий (1 ≤ n ≤ 105).

Далее следует описание событий.

Первая строка содержит одно целое число t — тип события (|t| = 1).

Если t = 1, то в новый офис переведён сотрудник из старого офиса. Тогда вторая строка содержит одно целое число D — номер отдела, в который зачислен сотрудник (1 ≤ D ≤ 109), следующая строка содержит имя сотрудника — непустое слово, состоящее из не более, чем 10 строчных латинских букв, третья строка содержит дату рождения сотрудника в Межгалактическом формате dd: mm: yyyy, где dd — день, mm — месяц и yyyy — год, 00 ≤ dd, mm ≤ 99, 0001 ≤ yyyy ≤ 9999. Гарантируется, что имена всех сотрудников попарно различны.

Если t =  - 1, то из нового офиса переводится сотрудник в старый. В этом случае вторая строка содержит два целых числа D и k — номер отдела, из которого переводится сотрудник, и локальный идентификатор данного сотрудника (1 ≤ D ≤ 109). Гарантируется, что k не превосходит общего количества прибытий в данный отдел на момент запроса и что для каждой пары D, k не существует более одного запроса с этой парой.

Выходные данные

Для каждого события выведите два имени, разделённых пробелами: имя руководителя офиса и имя руководителя отдела, к которому относится событие. Если офис или соответствующий отдел пуст, выведите "Vacant".

Пример
Входные данные
8
1
10
rab
01:01:0001
1
1000000000
tor
02:01:0001
-1
10 1
1
10
tur
01:01:0001
-1
10 2
-1
1000000000 1
1
5
bor
99:99:9999
1
5
rot
99:99:9999
Выходные данные
rab rab
rab tor
tor Vacant
tur tur
tor Vacant
Vacant Vacant
bor bor
bor bor
Примечание

Разберём пример.

Первое событие: в отдел 10 прибыл новый сотрудник rab. Он получил локальный идентификатор 1; так как больше сотрудников в отделе и офисе нет, то он стал руководителем отдела и руководителем офиса.

Второе событие: в отдел 1000000000 прибыл новый сотрудник tor. Он получил локальный идентификатор 1 в своём отделе, стал руководителем отдела, но не стал руководителем офиса, так как rab старше его.

Третье событие: из отдела 10 убыл сотрудник с локальным идентификатором 1, то есть rab. Главой офиса стал tor как единственный сотрудник в офисе, 10-й отдел остался пустым, так что выводим "Vacant".

Четвёртое событие: в отдел 10 прибыл сотрудник tur. Он получил локальный идентификатор 2 (так как это второе зафиксированное прибытие в этот отдел), стал новым руководителем отдела и стал новым руководителем всего офиса, так как он старше, чем tor.

Пятое событие: из отдела 10 убыл сотрудник с локальным идентификатором 2, то есть tur. В отделе никого не осталось, руководителем офиса снова стал tor.

Шестое событие: из отдела 1000000000 убыл сотрудник с локальным идентификатором 1, то есть tor. Ни в отделе, ни в офисе сотрудников не осталось, так что два раза выводим "Vacant".

Седьмое событие: в отдел 5 прибыл новый сотрудник bor. Он получил локальный идентификатор 1, так как больше сотрудников в отделе и офисе нет, то он стал руководителем отдела и руководителем офиса.

Восьмое событие: в отдел 5 прибыл новый сотрудник rot и получил локальный идентификатор 2. Он родился в тот же день, что и bor, но так как его локальный идентификатор больше, он не стал руководителем отдела. Аналогично он не стал руководителем офиса, так как у него те же дата рождения и номер отдела, что и у bor, но локальный идентификатор больше.